Cod sursa(job #1206677)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 10 iulie 2014 21:26:10
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <algorithm>
#include <vector>

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

int din[NMAX];
int v[NMAX];
int prev[NMAX];
vector<int> sol;

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

    v[0]=-INF;

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

    for(int i=1;i<=n;i++){
        din[i]=INF;

        int maxim=-INF;
        for(int j=i-1;j>=0;j--)
            if(v[j]<v[i]){
                if(v[j]>=maxim){
                    if(din[i]>(1+din[j])){
                        din[i]=(1+din[j]);
                        prev[i]=j;
                    }

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

    for(int i=n;i;i=prev[i])
        sol.push_back(i);
    reverse(sol.begin(),sol.end());

    cout<<sol[0];
    for(int i=1;i<sol.size()-1;i++)
        cout<<' '<<sol[i];
    cout<<'\n';

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