Pagini recente » Cod sursa (job #1429304) | Cod sursa (job #2691219) | Cod sursa (job #349513) | Cod sursa (job #500178) | Cod sursa (job #1599988)
#include<cstdio>
using namespace std;
const int nMax = 5000 + 1, INF = 1000001;
int v[nMax], d[nMax], urm[nMax];
int main (){
FILE *in = fopen("subsir2.in","r");
FILE *out = fopen("subsir2.out","w");
int n, minNr;
fscanf(in,"%d", &n);
for(int i = 1 ; i <= n ; ++i) fscanf(in,"%d", v + i);
v[0] = -INF;
for(int i = n; i >= 0 ; --i){
d[i] = minNr = INF;
for(int j = i + 1 ; j <= n ; ++j){
if(v[j] >= v[i] && v[j] < minNr){
minNr = v[j];
if((d[j] + 1 < d[i]) || (d[j] + 1 == d[i] && v[urm[i]] > v[j])){
d[i] = d[j] + 1;
urm[i] = j;
}
}
}
if(d[i] == INF){
d[i] = 1;
urm[i] = n + 1;
}
}
fprintf(out,"%d\n", d[0] - 1);
for(int i = urm[0] ; i <= n ; i = urm[i]){
fprintf(out,"%d ", i);
}
fprintf(out,"\n");
return 0;
}