Pagini recente » Cod sursa (job #394664) | Istoria paginii runda/dsadsa/clasament | Cod sursa (job #987536) | Cod sursa (job #1592364) | Cod sursa (job #982849)
Cod sursa(job #982849)
#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 ind,n,MAX;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
ind=-1;p[i]=-1;d[i]=1000000;
for(int j=i-1;j>=1;j--)
if(a[j]<=a[i])
{
if(ind==-1 || a[ind]<a[j])
ind=j;
if(d[i]>d[ind]+1 || (d[i]==d[ind]+1 && a[ind]<a[p[i]]))
{
d[i]=d[ind]+1;
p[i]=ind;
}
}
if(d[i]==1000000)
d[i]=1;
}
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);
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;
}