Cod sursa(job #1146465)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 18 martie 2014 23:28:17
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>

using namespace std;

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

int n,i,j,minim,vmin,Min,imin,ok;
int t[5005],d[5005],v[5005];

int main () {

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];

    d[n]=1;t[n]=-1;
    for (i=n-1;i>=1;i--) {

        minim=vmin=Min=1000000001;

        ok=1;
        for (j=i+1;j<=n;j++) {
            if (v[j]<minim && v[j]>=v[i]) {
                ok=0;
                minim=v[j];
                if (d[j]<Min) {
                    vmin=v[j];
                    Min=d[j];
                    t[i]=j;
                }else
                    if (d[j]==Min && v[j]<vmin) {
                        vmin=v[j];
                        t[i]=j;
                    }
            }
        }
        if (ok) {
           d[i]=1;
           t[i]=-1;
        }else
            d[i]=Min+1;
    }

    minim=vmin=1000000001;
    for (i=1;i<=n;i++) {
        if (v[i]<vmin){
            if (d[i]<minim) {
                minim=d[i];
                imin=i;
            }else
                if (d[i]==minim && v[imin]>v[i])
                    imin=i;
            vmin=v[i];
        }
    }
    fout<<minim<<"\n";
    while (imin!=-1){
        fout<<imin<<" ";
        imin=t[imin];
    }

    return 0;
}