Cod sursa(job #1767373)

Utilizator Bodo171Bogdan Pop Bodo171 Data 28 septembrie 2016 22:37:45
Problema Subsir 2 Scor 83
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include<fstream>
using namespace std;
int nxt[5005],best[5005],maxim,minim,mn,minbest,v[5005],i,j,n,poz,minpoz,mx;
int main()
{
    ifstream f("subsir2.in");
    ofstream g("subsir2.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i];
    }
    for(i=1;i<=n;i++)
        best[i]=(1<<30);
    maxim=-(1<<30);
    minim=(1<<30);
    for(i=n;i>=1;i--)
    {
        if(v[i]>maxim)
        {
            maxim=v[i];
            best[i]=1;
        }
        mx=-(1<<30);
        for(j=i-1;j>=1;j--)
        {
            if(v[j]>mx&&v[j]<=v[i])
            {
                mx=v[j];
                if(best[i]+1<best[j]||(best[i]+1==best[j]&&v[i]<v[nxt[j]]))
                {
                    best[j]=best[i]+1;
                    nxt[j]=i;
                }
            }
        }
    }
    minbest=(1<<30);minpoz=(1<<30);
    for(i=1;i<=n;i++)
    {
      if(v[i]<minim)
        {
            minim=v[i];
            if(best[i]<minbest)
        {
            minbest=best[i];
            minpoz=i;
            poz=i;
        }
        }
    }
    g<<minbest<<'\n';
    for(i=1;i<=minbest;i++)
    {
        g<<poz<<' ';
        poz=nxt[poz];
    }
    return 0;
}