Cod sursa(job #982849)

Utilizator dariusdariusMarian Darius dariusdarius Data 10 august 2013 12:45:13
Problema Subsir 2 Scor 49
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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 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;
}