Cod sursa(job #1206695)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 10 iulie 2014 22:40:10
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <vector>

#define NMAX 5005
#define INF 1000005
using namespace std;

int v[NMAX];

int din[NMAX];
int prec[NMAX];

int main()
{
    ifstream cin("subsir2.in");
    ofstream cout("subsir2.out");

    int n=0;
    cin>>n;
    if(!n)
        return 0;

    for(int i=1;i<=n;i++)
        cin>>v[i];
    v[0]=-INF;
    v[++n]=INF;

    for(int i=n-1;i>=0;i--){
        din[i]=INF;

        int minim=INF+1;
        for(int j=i+1;j<=n;j++)
            if(v[j]>=v[i]){
                if(v[j]<minim){
                    if(din[i]>(1+din[j])){
                        din[i]=(1+din[j]);
                        prec[i]=j;
                    }
                    else if(din[i]==(1+din[j]))
                        if(v[i]<v[prec[i]])
                            prec[i]=j;

                    minim=v[j];
                }
            }
    }
    cout<<din[0]-1<<'\n';

    cout<<prec[0];
    for(int i=prec[0];prec[i]!=n;i=prec[i])
        cout<<' '<<prec[i];

    cin.close();
    cout.close();
    return 0;
}