Pagini recente » Cod sursa (job #643487) | Istoria paginii runda/igorj_9 | Istoria paginii runda/uvs_runda_1 | Cod sursa (job #1719614) | Cod sursa (job #982844)
Cod sursa(job #982844)
#include<cstdio>
#include<vector>
using namespace std;
int a[5005];
int d[5005];
int p[5005];
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int n,MAX;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
MAX=-1000001;p[i]=-1;d[i]=1;
for(int j=i-1;j>=1;j--)
if(a[j]>MAX && a[j]<=a[i])
{
if(d[i]<d[j]+1 || (d[i]==d[j]+1 && a[j]<a[p[i]]))
d[i]=d[j]+1,p[i]=j;
MAX=a[j];
}
}
int ind=1;MAX=d[1];
for(int i=2;i<=n;i++)
if(MAX<d[i] || (MAX==d[i] && a[i]<a[ind]))
MAX=d[i],ind=i;
printf("%d\n",MAX-1);
vector<int> sol;
while(ind!=-1)
{
sol.push_back(ind);
ind=p[ind];
}
for(vector<int>::reverse_iterator it=sol.rbegin();it!=sol.rend();it++)
printf("%d ",*it);
printf("\n");
return 0;
}