Cod sursa(job #1967736)

Utilizator razvandRazvan Dumitru razvand Data 17 aprilie 2017 00:10:51
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int v[100003];
int dp[100003];
int ba[100003];
bool u[100003];

int main() {

    int n;
    in >> n;

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

    dp[n] = 1;
    ba[n] = -1;

    for(int i = n-1; i >= 1; i--) {
        int bst = 0;
        for(int j = i+1; j <= n; j++) {
            if(v[j] >= v[i]) {
                u[j] = 1;
                if(dp[j] > dp[bst] || j == 0)
                    bst = j;
                else if(dp[j] == dp[bst] && v[j] < v[bst])
                    bst = j;
            }
        }
        if(bst == 0) {
            dp[i] = 1;
            ba[i] = -1;
            continue;
        }
        dp[i] = dp[bst]+1;
        ba[i] = bst;
    }

    int mx = 0;

    for(int i = 1; i <= n; i++) {
        if(u[i] == 0) {
            if(mx == 0 || dp[i] < dp[mx]) {
                mx = i;
            } else if(dp[i] == dp[mx] && v[i] < v[mx]) {
                mx = i;
            }
        }
    }

    out << dp[mx] << '\n';
    while(mx != -1) {
        out << mx << " ";
        mx = ba[mx];
    }

    return 0;
}