Cod sursa(job #1668428)

Utilizator sebastiannrxRichiteanu Mihai Sebastian sebastiannrx Data 29 martie 2016 19:52:21
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n,a,i,nr,j,ma,lc,mi,k,v[5010],s[5010],l[5010];
int main()
{   f>>n;
    for (i=1;i<=n;++i)
        f>>v[i];
    l[n]=1;
    s[n]=n;
    v[0]=-40000000;
    for (i=n;i>=0;--i) {
        mi=40000000;
        l[i]=40000000;
        for (j=i+1;j<=n;++j)
           if (v[j]<mi && v[i]<=v[j]) {
                mi=v[j];
                nr=l[j]+1;
                if (l[i]==nr && v[j]<v[s[i]])
                    s[i]=j;
                if (nr<l[i]) {
                    l[i]=nr;
                    s[i]=j;}}

        if (l[i]==40000000) {
            l[i]=1;
            s[i]=i;}}



    g<<l[0]-1<<'\n';
    k=0;
    while (k!=s[k]) {

        k=s[k];
        g<<k<<" ";
    }
    g<<'\n';



    return 0;
}