Cod sursa(job #1208071)

Utilizator mihaimusatMihai Musat mihaimusat Data 14 iulie 2014 16:48:42
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>

using namespace std;

int n,i,valmin,Min,x,j;

int v[5005],d[5005],t[5005];

int main() {
    ifstream f("subsir2.in");
    ofstream g("subsir2.out");

    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    d[n]=1;
    t[n]=0;
    for(i=n-1;i>=1;i--) {
        Min=valmin=x=2000000000;
        for(j=i+1;j<=n;j++) {
            if(v[j]<Min && v[j]>=v[i]) {
                Min=v[j];
                if(x==d[j] && v[j]<valmin) {
                    valmin=v[j];
                    t[i]=j;
                }
                if(d[j]<x) {
                    valmin=v[j];
                    x=d[j];
                    t[i]=j;
                }
            }
        }
        if(x!=2000000000)
            d[i]=x+1;
        else {
            d[i]=1;
            t[i]=0;
        }
    }
    valmin=Min=x=2000000000;
    for(i=1;i<=n;i++)
        if(valmin>v[i]) {
            if(d[i]==Min && v[i]<v[x])
                x=i;
            if(d[i]<Min) {
                Min=d[i];
                x=i;
            }
            valmin=v[i];
        }
    g<<Min<<"\n"<<x<<" ";
    for(;t[x]!=0;x=t[x])
        g<<t[x]<<" ";
    return 0;
}