Cod sursa(job #3288959)

Utilizator Allie28Radu Alesia Allie28 Data 24 martie 2025 22:54:03
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

const int LMAX = 5005;
const int INF = 0x3f3f3f3f;
const ll MOD = 1000000007;

//dp[i] --> lungimea subsirului ... pana la pozitia i
int dp[LMAX], v[LMAX], prv[LMAX];

int main() {
    int n, i, j, poz;
    fin>>n;
    for (i = 1; i <= n; i++) {
        fin>>v[i];
    }
    v[0] = -INF;
    v[n + 1] = INF;
    for (i = n; i >= 0; i--) {
        dp[i] = n + 1;
        poz = -1;
        for (j = i + 1; j <= n + 1; j++) {
            if ((poz == - 1 || v[j] < v[poz]) && v[j] >= v[i]) {
                if (dp[i] >= dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    prv[i] = j;
                }
                poz = j;
            }
        }
    }
    fout<<dp[0] - 1<<"\n";
    i = 0;
    vector<int> ans;
    while (prv[i] != n + 1) {
        ans.push_back(prv[i]);
        i = prv[i];
    }
    for (i = 0; i < ans.size(); i++) {
        fout<<ans[i]<<" ";
    }


    fin.close();
    fout.close();
    return 0;
}