Cod sursa(job #2712025)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 25 februarie 2021 08:31:10
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

const int NMAX = 5005;
int N, a[NMAX], dp[NMAX], nxt[NMAX];

void min_self(int &a, int b) {
    a = min(a, b);
}

int main() {
    fin >> N;
    for(int i = 1; i <= N; ++i)
        fin >> a[i];
    for(int i = N; i > 0; --i) {
        dp[i] = INF;
        bool found = false;
        int between = INF;
        for(int j = i + 1; j <= N; ++j)
            if(a[i] <= a[j] && a[j] < between) {
                if(dp[i] > dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    nxt[i] = j;
                }
                else
                    if(dp[i] == dp[j] + 1 && a[j] < a[nxt[i]])
                        nxt[i] = j;
                found = true;
                between = a[j];
            }
        if(!found) {
            dp[i] = 1;
            nxt[i] = -1;
        }
    }
    int between = INF, best = INF, start = 1, prv = INF;
    for(int i = 1; i <= N; ++i) {
        if(between <= a[i])
            continue;
        if(dp[i] < best) {
            best = dp[i];
            start = i;
            prv = a[i];
        }
        else
            if(dp[i] == best && a[i] < prv) {
                start = i;
                prv = a[i];
            }
        between = a[i];
    }
    fout << best << '\n';
    while(start != -1) {
        fout << start << ' ';
        start = nxt[start];
    }
    fout << '\n';
}