Cod sursa(job #2202218)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 7 mai 2018 21:31:54
Problema Subsir 2 Scor 83
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<fstream>
using namespace std;
ifstream fi("subsir2.in");
ofstream fo("subsir2.out");
int n,i,j,k,Dp[5005],A[5005],Rec[5005],rez,ind,minim;
int main()
{
    fi>>n;
    for(i=1; i<=n; i++)
        fi>>A[i];
    Dp[n]=1;
    Rec[n]=n+1;
    for(i=n-1; i>=1; i--)
    {
        k=1000000000;
        Dp[i]=1000000000;
        Rec[i]=n+1;
        for(j=i+1; j<=n; j++)
        {
            if(A[j]>=A[i] && A[j]<k)
            {
                if(Dp[j]+1<Dp[i])
                {
                    Dp[i]=Dp[j]+1;
                    Rec[i]=j;
                }
                else
                    if(Dp[j]+1==Dp[i] && A[j]<A[Rec[i]])
                        Rec[i]=j;
            }
            if(A[j]>=A[i])
                k=min(k,A[j]);
        }
        if(Dp[i]==1000000000)
            Dp[i]=1;
    }
    minim=rez=1000000000;
    for(i=1; i<=n; i++)
    {
        if(A[i]<minim)
        {
            minim=A[i];
            if(rez>Dp[i])
            {
                rez=Dp[i];
                ind=i;
            }
        }
    }
    fo<<rez<<"\n";
    while(ind!=n+1)
    {
        fo<<ind<<" ";
        ind=Rec[ind];
    }
    fi.close();
    fo.close();
    return 0;
}