Cod sursa(job #874883)

Utilizator dtoniucDaniel Toniuc dtoniuc Data 9 februarie 2013 13:35:43
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 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;
        best[i]=INF;
        for(int j=i+1;j<=n;j++)
            if(v[j]>=v[i] && v[j]<max)
            {
                viz[j]=true;
                if(best[j]+1<best[i] || best[j]+1 == best[i] && v[j]<v[next[i]])
                {
                    best[i]=best[j]+1;
                    next[i]=j;
                }
                max=v[j];
            }
        if(best[i]==INF) best[i]=1;
    }

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

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