Pagini recente » Cod sursa (job #248983) | Cod sursa (job #1382751) | Cod sursa (job #35224) | Cod sursa (job #2315918) | Cod sursa (job #1646774)
#include<fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int poz[100001];
int l[5005];
int v[5005];
int prov[5005];
int maxu[5005];
int n;
int main(){
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i];
poz[n]=-1;
l[n]=1;
int j;
for(int i=n-1;i>0;i--)
for(poz[i]=-1,l[i]=1,maxu[i]=1000005,j=i+1;j<=n;j++)
if(v[i]<=v[j]){
prov[j]=1;
if(poz[i]==-1){
l[i]=l[j]+1;
poz[i]=j;
}
else if(v[j]<maxu[i]&&l[i]>=1+l[j]){
poz[i]=j;
l[i]=1+l[j];
}
if(maxu[i]>v[j])maxu[i]=v[j];
}
int maxi=1,maxl=5002;
for(int i=1;i<=n;i++)
if(maxl>l[i]&&prov[i]==0){maxl=l[i];maxi=i;}
else if(maxl==l[i]&&prov[i]==0&&v[maxi]>v[i]){maxl=l[i];maxi=i;}
fout<<maxl<<'\n';
do{
fout<<maxi<<" ";
maxi=poz[maxi];
}while(maxi!=-1);
fout<<'\n';
fin.close();
fout.close();
}