Cod sursa(job #1206691)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 10 iulie 2014 22:29:25
Problema Subsir 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <algorithm>
#include <vector>

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

int v[NMAX];

int din[NMAX];
int prec[NMAX];
vector<int> sol;

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;
                    }

                    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;
}