Cod sursa(job #2247397)

Utilizator YetoAdrian Tonica Yeto Data 28 septembrie 2018 16:03:08
Problema Subsir 2 Scor 97
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
using namespace std;
int n, i, j, minim=1000001, v[5011], l[5011], tata[5011],mini=1000001,pmin;
int pos;

int main () {
    ifstream fin ("subsir2.in");
    ofstream fout ("subsir2.out");
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>v[i];
        if(v[i]<minim){
            minim=v[i];
            pmin=i;
        }

    }
int    p=0;
    l[0]=mini;
    for (i=n;i>=1;i--) {
            l[i]=1;p=0;mini=1000001;
        for (j=i+1;j<=n;j++) {
            if (v[j]>=v[i]&&v[j]<mini) {
                  if(l[j]<=l[p]){
                     l[i]=l[j]+1;
                     tata[i]=j;
                      p=j;
                  }
               mini=v[j];
            }
        }
    }

    int r=0; int Min=1000001, lmin=1000001;
    for (i=1;i<=pmin;i++) {

            if (v[i]<Min && l[i]<=lmin){
                Min=v[i];
                lmin=l[i];
                pos=i;
            }

        }



    fout<<l[pos]<<'\n';
    while (pos>0) {
        fout<<pos<<" ";
        pos=tata[pos];
    }

    return 0;
}