Cod sursa(job #2056154)

Utilizator DavidDragulinDragulin David DavidDragulin Data 4 noiembrie 2017 09:24:19
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n,sol[5005],bf[5005],v[5005],i,j,min1,p,s;
int main()
{
    fin>>n;
    for (i=1;i<=n;++i)
        fin>>v[i];
    for (i=n;i>=1;--i)
    {
        min1=1e9;
        s=min1;
        for (j=i+1;j<=n;++j)
            if ((v[j]>=v[i]) && (v[j]<min1))
                {
                    min1=v[j];
                    if (sol[j]<=s)
                        s=sol[j],p=j;
            }
        if (min1==1e9)
            sol[i]=1;
        else
                sol[i]=sol[p]+1,bf[i]=p;
    }
    min1=sol[1],p=1,j=v[1];
    for (i=2;i<=n;++i)
        if (v[i]<j)
        {
            j=v[i];
            if (sol[i]<=min1)
                min1=sol[i],p=i;
        }
    fout<<min1<<'\n';
    fout<<p<<" ";
    while(--min1)
    {
        p=bf[p];
        fout<<p<<" ";
    }

return 0;
}