Cod sursa(job #2676855)

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

using namespace std;

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

int n, v[5005], lung, p[5005], dp[5005];

int main(){
    fin >> n;
    for (int i = 1; i <= n; ++i){
        fin >> v[i];
    }
    dp[n] = 1;
    p[n] = -1;
    for (int i = n - 1; i >= 1; --i){
        dp[i] = 1e9;
        int maxx = 1e9;
        bool gasit = false;
        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]){
                    if (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[n] = -1;
        }
    }
    int minim = v[1], minimdp = dp[1], pos = 1;
    for (int i = 2; i <= n; ++i){
        if (v[i] < minim){
            if (dp[i] < minimdp){
                minimdp = dp[i];
                pos = i;
            }
            else if (dp[i] == minim){
                if (v[i] < minim){
                    minim = v[i];
                    pos = i;
                }
            }
        }
        minim = min(minim, v[i]);
    }
    fout << minimdp << "\n";
    while (pos != -1){
        fout << pos << " ";
        pos = p[pos];
    }
    fin.close();
    fout.close();
    return 0;
}