Cod sursa(job #2676863)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 25 noiembrie 2020 09:53:23
Problema Subsir 2 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 5005;
int n, v[nmax], dp[nmax], p[nmax];

int main(){
    fin >> n;
    for (int i = 1; i <= n; ++i){
        fin >> v[i];
    }
    for (int i = n; i >= 1; --i){
        dp[i] = 1e9;
        bool gasit = false;
        int maxx = 1e9;
        for (int j = i + 1; j <= n; ++j){
            if (v[j] >= v[i] && maxx > v[j]){
                if (1 + dp[j] < dp[i]){
                    dp[i] = 1 + dp[j];
                    p[i] = j;
                }
                else if (1 + dp[j] == dp[i] && v[j] < v[p[i]]){
                    p[i] = j;
                }
                gasit = true;
            }
            if (v[j] >= v[i]) maxx = min(maxx, v[j]);
        }
        if (!gasit){
            dp[i] = 1;
            p[i] = -1;
        }
    }
    int maxx = 1e9, minim = 1e9, pos, val;
    for (int i = 1; i <= n; ++i){
        if (maxx < v[i]){
            continue;
        }
        if (dp[i] < minim){
            minim = dp[i];
            pos = i;
            val = v[i];
        }
        else if (dp[i] == minim){
            if (v[i] < val){
                val = v[i];
                pos = i;
            }
        }
        maxx = min(maxx, v[i]);
    }
    fout << minim << "\n";
    while (pos != -1){
        fout << pos << " ";
        pos = p[pos];
    }
    fin.close();
    fout.close();
    return 0;
}