Nu aveti permisiuni pentru a descarca fisierul grader_test14.in
Cod sursa(job #1599988)
| Utilizator | Data | 14 februarie 2016 16:23:06 | |
|---|---|---|---|
| Problema | Subsir 2 | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.97 kb |
#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;
}
