Pagini recente » Cod sursa (job #850754) | Cod sursa (job #3188502) | Cod sursa (job #844763) | Cod sursa (job #1203141) | Cod sursa (job #1386835)
#include <stdio.h>
#define INF 1000000000
#define MAXN 5000
int d[MAXN+1], v[MAXN+1], next[MAXN+1];
int main(){
int n, i, j, p, min;
FILE *fin, *fout;
fin=fopen("subsir2.in", "r");
fout=fopen("subsir2.out", "w");
fscanf(fin, "%d", &n);
v[0]=-INF;
for(i=1; i<=n; i++){
fscanf(fin, "%d", &v[i]);
}
for(i=n; i>=0; i--){
min=d[i]=INF;
for(j=i+1; j<=n; j++){
if((v[j]>=v[i])&&(v[j]<min)){
min=v[j];
if((d[i]>d[j]+1)||((d[i]==d[j]+1)&&(v[j]<v[next[i]]))){
d[i]=d[j]+1;
next[i]=j;
}
}
}
if(d[i]==INF){
d[i]=1;
next[i]=n+1;
}
}
fprintf(fout, "%d\n%d", d[0]-1, next[0]);
p=next[next[0]];
while(p!=n+1){
fprintf(fout, " %d", p);
p=next[p];
}
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}