Cod sursa(job #982845)

Utilizator dariusdariusMarian Darius dariusdarius Data 10 august 2013 12:33:04
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#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);
    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;
}