Cod sursa(job #2467706)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 4 octombrie 2019 21:22:43
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5005;

int v[MAXN], dp[MAXN];

int main()
{
    ifstream fin("subsir2.in");
    ofstream fout("subsir2.out");
    int n;
    fin >> n;
    for(int i = 1; i <= n; ++i){
        fin >> v[i];
        dp[i] = 1e9;
    }
    dp[n] = 1;
    for(int i = n - 1; i >= 1; --i){
        int mn = 1e9;
        for(int j = i + 1; j <= n; ++j){
            if(v[i] <= v[j] && v[j] < mn){
                mn = v[j];
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        if(dp[i] == 1e9) dp[i] = 1;
    }
    int mnval = 1e9, minlen = 1e9;
    for(int i = 1; i <= n; ++i){
        if(v[i] < mnval){
            mnval = v[i];
            minlen = min(minlen, dp[i]);
        }
    }
    fout << minlen << "\n";
    int pos = 0, last = -1e9;
    while(minlen){
        int next = 1e9;
        for(int i = pos + 1; i <= n; ++i){
            if(dp[i] == minlen && last <= v[i] && v[i] < next){
                next = v[i];
                pos = i;
            }
            else if(last <= v[i] && v[i] < next) next = v[i];
        }
        fout << pos << " ";
        last = v[pos];
        minlen--;
    }
    return 0;
}