Cod sursa(job #1291415)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 12 decembrie 2014 19:28:26
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
using namespace std;
ifstream f("subsir2.in"); ofstream g("subsir2.out");
const int inf=1000001;
int n,i,j,min1,p,s,sol[5001],bf[5001],v[5001];
int main()
{   f>>n;
    for(i=1;i<=n;++i) f>>v[i];
    for(i=n;i>0;--i)
    {   min1=s=inf;
        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==inf) 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;
        }
    g<<min1<<"\n"<<p<<" ";
    min1--;
    while(min1) {min1--; p=bf[p]; g<<p<<" ";}
    return 0;
}