Cod sursa(job #1911655)

Utilizator GoogalAbabei Daniel Googal Data 7 martie 2017 21:17:58
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#define nm 5001
#define INF 1<<30

using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

int n,a[nm],best[nm],t[nm],rez=INF,poz,minn=INF;
bool ok[nm];

void read()
{
    int i;
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>a[i];
        if(a[i]>=minn)
            continue;
        ok[i]=true;
        minn=a[i];
    }
    fin.close();
}

int main()
{
    int i,j;
    read();
    for(i=n; i>0; i--)
    {
        best[i]=minn=INF;
        t[i]=-1;
        for(j=i+1; j<=n; j++)
        {
            if(a[i]>a[j])
                continue;
            if(a[j]<minn && (best[i]>best[j]+1 || (best[i]==best[j]+ 1 && a[j]<a[t[i]])))
            {
                best[i]=best[j]+1;
                t[i]=j;
            }
            if(a[j]<minn)
                minn=a[j];
        }
        if(best[i]==INF)
        {
            best[i]=1;
            t[i]=i;
        }
        if(ok[i] && (rez>best[i] || (rez==best[i] && a[poz]>a[i])))
        {
            rez=best[i];
            poz=i;
        }
    }

    fout<<rez<<'\n';
    for(i=poz; i!=t[i] ; i=t[i])
        fout<<i<<' ';
    fout<<i;
    fout.close();
    return 0;
}