Cod sursa(job #950637)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 17 mai 2013 13:40:16
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
using namespace std;
ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");

int s[5001],v[5001],j,succ[5001],i,n;
bool pred[5001];

int main ()
{
    fin>>n;
    for (i=1;i<=n;i++) fin>>v[i];
    succ[n]=0;
    for (i=n-1;i>=1;i--)
    {
        for (j=i+1;j<=n;j++)
        {
            if (s[i]==0) {if(v[i]<=v[j])  s[i]=j;}
            else if (v[i]<=v[j] && v[j]<v[s[i]] && succ[j]<=succ[s[i]]) s[i]=j;
        }
        if (s[i]) {succ[i]=succ[s[i]]+1; pred[s[i]]=1;}
    }
    int minm=5001,mini;
    for (i=1;i<=n;i++)
    {
        if (pred[i]==0) if (succ[i]<minm || (succ[i]==minm && v[i]<v[mini])) {mini=i; minm=succ[i];}
    }
    fout<<succ[mini]+1<<"\n"<<mini<<" ";
    while (s[mini])
    {
        mini=s[mini];
        fout<<mini<<" ";
    }
}