Cod sursa(job #2631236)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 29 iunie 2020 15:50:45
Problema Subsir 2 Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>
#define maxn 5005

std::ifstream fin ("subsir2.in");
std::ofstream fout ("subsir2.out");

int dp[maxn], x[maxn], next[maxn];
bool ok[maxn];

int main()
{
    int n, i, j;
    fin >> n;
    for (i=0; i<n; i++)
        fin >> x[i];

    dp[n-1] = 1;
    for (i=n-2; i>=0; i--){
        dp[i] = 1;
        for  (j=i+1; j<n; j++){
            if (x[j] >= x[i]){
                ok[j] = true;
                if (dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    next[i] = j;
                }
                else if (dp[i] == dp[j] + 1)
                     if (x[next[i]] > x[j])
                     next[i] = j;
            }
        }
    }

    /*
    for (i=0; i<n; i++)
        fout << dp[i] << ' ';
    fout << '\n';
    for (i=0; i<n; i++)
        fout << ok[i] << ' ';
    */

    int pos = -1, max=1e9;
    for (i=0; i<n; i++){
        if (ok[i] == false){
            if (max > dp[i]){
                max = dp[i];
                pos = i;
            }
            else if (max == dp[i] and x[pos] > x[i])
                pos = i;
        }

    }
    fout << max << '\n';
    fout << pos + 1 << ' ';

    while (next[pos] != 0){
        pos = next[pos];
        fout << pos + 1 << ' ';
    }

    return 0;
}