Cod sursa(job #2697848)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 19 ianuarie 2021 23:42:42
Problema Subsir 2 Scor 2
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("subsir2.in");
ofstream fout("subsir2.out");
const int nmax = 5000 + 50;

int n, a[nmax], dp[nmax], rez[nmax];
bool marked[nmax];

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> a[i];

    }

    for (int i = 1; i <= n; ++i) {
        bool ok = false;
        marked[i] = true;
        int nr, pos = 0;
        for (int j = i - 1; j >= 1; j --) {
            if (!ok) {
                if (a[j] <= a[i]) {
                    dp[i] = dp[j];
                    nr = a[j];
                    pos = j;
                    ok = true;
                }
            }
            else {
                if (a[j] <= a[i] && a[j] >= nr) {
                    if (dp[j] < dp[i]) {
                        dp[i] = dp[j];
                        marked[pos] = true;
                        nr = dp[j];
                        pos = j;
                    }
                }
            }

            marked[pos] = false;
        }
        dp[i] ++;
    }

    int mini = INT_MAX, pos = 0;
    for (int i = 1; i <= n; ++ i) {
        if (marked[i] && dp[i] <= mini) {
            mini = dp[i];
            pos = i;
        }
    }

    fout << mini << '\n';
    int k = 0, nr = a[pos];
    for (int i = pos; i >= 1; --i) {
        if (dp[i] == mini && a[pos] >= a[i]) {
            rez[++k] = i;
            mini --;
        }
    }

    for (int i = k; i >= 1; --i)
        fout << rez[i] << ' ';
    return 0;
}