Cod sursa(job #2780185)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 6 octombrie 2021 12:20:06
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
#define N 5005
#define INF 1000000000
int n, minn, poz, val, a[N], dp[N], p[N], b[N];
int main() {
    fin >> n;
    for (int i=1;i<=n;i++){
        fin >> a[i];
        dp[i] = (1 << 30);
    }

    for (int i=n;i>=1;--i){
        val = (1 << 30);
        for (int j=i+1;j<=n;j++){
            if (a[i] <= a[j]){
                b[j] = 1;
                if (a[j] < val){
                    if (dp[i] >= dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        p[i] = j;
                    }
                    val = a[j];
                }
            }
        }
        if (dp[i] > n)
            dp[i] = 1;
    }

    int rez = 0;
    dp[0] = (1 << 30);
    for (int i=1;i<=n;i++){
        if (b[i] == 0 && (dp[rez] > dp[i] || (dp[rez] == dp[i] && a[rez] > a[i])))
            rez = i;
    }
    fout << dp[rez] << '\n';
    for ( ;rez != 0;rez = p[rez])
        fout << rez << ' ';
    return 0;
}