Cod sursa(job #1145774)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 18 martie 2014 13:47:13
Problema Subsir 2 Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>

using namespace std;

int n,i,Max,Min,j,poz,minim;

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

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++) {
        Max=0;
        for(j=1;j<i;j++)
            if(v[j]<v[i] && d[j]>Max)
                Max=d[j];
        d[i]=Max+1;
    }
    for(i=n;i>=1;i--) {
        Max=0;
        for(j=i+1;j<=n;j++)
            if(v[j]>v[i] && l[j]>Max)
                Max=l[j];
        l[i]=Max+1;
    }
    Min=n+1;
    for(i=1;i<=n;i++)
        if(Min>d[i] && l[i]==1)
            Min=d[i];
    for(i=1;i<=n;i++)
        if(Min>l[i] && d[i]==1)
            Min=l[i];
    g<<Min<<"\n";
    poz=1;
    for(i=Min;i>=1;i--) {
        minim=1000000000;
        for(j=poz;j<=n;j++)
            if(l[j]==i && v[j]<minim) {
                minim=v[j];
                poz=j+1;
            }
            g<<poz-1<<" ";
    }
    return 0;
}