Cod sursa(job #874568)

Utilizator dtoniucDaniel Toniuc dtoniuc Data 8 februarie 2013 20:27:48
Problema Subsir 2 Scor 58
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#define INF 1<<30
using namespace std;

int n;
bool viz[5005];
int v[5005],next[5005],best[5005];
int main()
{
    ifstream fin("subsir2.in");
    ofstream fout("subsir2.out");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];

    for(int i=n;i>=1;i--)
    {
        int max=INF;
        int l=INF;
        for(int j=i+1;j<=n;j++)
            if(v[j]>v[i])
            {
                viz[j]=false;
                if(v[j]<max && best[j]+1<=l)
                {
                    l=best[j]+1;
                    best[i]=l;
                    next[i]=j;
                    max=v[j];
                }
            }
        viz[i]=true;
        if(best[i]==0) best[i]=1;
    }

    int min=INF,poz=0;
    for(int i=1;i<=n;i++)
        if(viz[i]==true && v[i]<min)
         {
             min=v[i];
             poz=i;
         }
    fout<<best[poz]<<'\n';

    while(poz)
    {
        fout<<poz<<" ";
        poz=next[poz];
    }
    return 0;
}