Pagini recente » Cod sursa (job #2846140) | Cod sursa (job #2238742) | Cod sursa (job #1433762) | Cod sursa (job #1932227) | Cod sursa (job #2398147)
#include <fstream>
using namespace std;
ifstream f ("subsir2.in");
ofstream g ("subsir2.out");
int n, v[5005];
int best[5005], poz[5005], l[5005], pos, nr;
bool ok[5005];
const int inf = (1 << 30);
int minim;
int gasit ( int i, int j ){
int li = i;
if(j == i + 1) return 0;
for(i = li + 1; i < j; i++)
if(v[li] <= v[i] && v[i] <= v[j])
return 1;
return 0;
}
void see ( int x ){
g << x << " ";
if(poz[x] >= 1)
see (poz[x]);
}
int main(){
int i, j;
f >> n;
if( n == 1){ g << 1 << "\n" << 1; return 0;}
minim = inf;
for(i = 1; i <= n ; i++){
f >> v[i];
if(v[i] < minim){
minim = v[i];
ok[i] = 1;
}
}
best[n] = 1;
poz[n] = -1;
int cmax = 0;
int pozmax = 0;
for(i = n-1; i >= 1 ; i--){
best[i] = inf;
minim = inf;
poz[i] = -1;
for(j = i + 1 ; j <= n ; j++){
if(minim > v[j] && (v[j] >= v[i] && (best[j] + 1 < best[i] || (best[i] == best[j] + 1 && v[j] < v[poz[i]]) ) /*&& !gasit(i,j)*/ )){
best[i] = best[j] + 1;
poz[i] = j; //g << j << " " << i << " " << gasit(i,j)<<"\n";
}
minim = min( minim, v[j] );
}
if(ok[i] && ( best[i] > cmax || (best[i] == cmax && v[i] < v[pozmax]) )){
cmax = best[i];
pozmax = i;
}
}
g << cmax << "\n";
see(pozmax);
// g << pozmax << "\n";
/*for(i = 1 ; i <= n; i++ )
g << best[i] << " "; g << "\n";
for(i = 1 ; i <= n; i++ )
g << poz[i] << " ";*/
return 0;
}