Mai intai trebuie sa te autentifici.
Cod sursa(job #1714486)
Utilizator | Data | 8 iunie 2016 14:49:31 | |
---|---|---|---|
Problema | Subsir 2 | Scor | 62 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.01 kb |
# include <fstream>
# define DIM 5010
# define INF 1000000000
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int v[DIM],l[DIM],t[DIM],sol[DIM],n,i,j,maxim,minim,poz,k;
int main () {
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i];
for(i=1;i<=n;i++){
maxim=0;
l[i]=INF;
for(j=i-1;j>=1;j--){
if(v[i]>=v[j]&&v[j]>=maxim){
maxim=v[j];
if(l[j]+1<l[i]){
l[i]=l[j]+1;
t[i]=j;
}
}
}
if(l[i]==INF)
l[i]=1;
}
maxim=0;
minim=INF;
for(i=n;i>=1;i--){
if(v[i]>=maxim){
maxim=v[i];
if(l[i]<minim){
minim=l[i];
poz=i;
}
}
}
fout<<minim<<"\n";
i=poz;
while(i!=0){
sol[++k]=i;
i=t[i];
}
for(i=k;i>=1;i--)
fout<<sol[i]<<" ";
fout<<"\n";
return 0;
}