Cod sursa(job #3288957)

Utilizator Allie28Radu Alesia Allie28 Data 24 martie 2025 22:43:18
Problema Subsir 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 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[n + 1] = INF;
    for (i = 1; i <= n + 1; i++) {
        dp[i] = n + 1;
        poz = -1;
        j = i - 1;
        while(j > 0) {
            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;
            }
            j--;
        }
        if (poz == -1) dp[i] = 1, prv[i] = 0;
    }
    fout<<dp[n + 1]<<"\n";
    i = n + 1;
    vector<int> ans;
    while (prv[i]) {
        ans.push_back(prv[i]);
        i = prv[i];
    }
    for (i = ans.size() - 1; i >= 0; i--) {
        fout<<ans[i]<<" ";
    }


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