Mai intai trebuie sa te autentifici.

Cod sursa(job #1489232)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 20 septembrie 2015 19:58:13
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
#define inf 5050

using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int N;
int v[5010],best[5010],urm[5010];
// v=vectorul initial
// best[i]=lungimea subsirului maximal de lungime minima ( pe [i,N] ) care se termina la stanga in i
// urm[i]=pozitia elementului urmator lui i in subsirul in care se afla i

int main()
{
    f>>N;
    FOR (i,1,N) {
        f>>v[i];
    }
    best[N]=1;
    urm[N]=inf;
    ROF (i,N-1,1) {
        best[i]=inf;
        urm[i]=inf;
        int min1=inf;
        FOR (j,i+1,N) {
            if (v[i]<=v[j] && v[j]<min1) {
                min1=v[j];
                if (best[i]>=best[j]) {
                    best[i]=best[j];
                    urm[i]=j;
                }
            }
        }
        if (best[i]==inf) {
            best[i]=1;
        }
        else {
            ++best[i];
        }
    }
    int j=1,st=1;
    int rez=best[1];
    FOR (i,2,N) { // se cauta cel mai scurt subsir maximal care incepe de pe un element cat mai mic
        if (v[j]>v[i]) {
            j=i;
            if (best[j]<=rez) {
                rez=best[j];
                st=i;
            }
        }
    }
    g<<rez<<'\n';
    while (st!=inf) {
        g<<st<<' ';
        st=urm[st];
    }
    f.close();g.close();
    return 0;
}