Cod sursa(job #1043145)

Utilizator ELHoriaHoria Cretescu ELHoria Data 28 noiembrie 2013 01:29:18
Problema Subsir 2 Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>

using namespace std;

ifstream cin("subsir2.in");
ofstream cout("subsir2.out");

const int nmax = 5002;
int n;
int a[nmax], dp[nmax], who[nmax];
int vmin = int(2e9);

void readData() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
}

void solve() {
    int bstPos = n + 1;
    dp[n + 1] = n;
    for (int i = n;i >= 1;i--) {
        who[i] = i;
        dp[i] = n + 1;
        vmin = min(vmin,a[i]);
        int aux = int(2e9);
        for(int j = i + 1;j <= n;j++) {
            if (a[j] >= a[i]) {
                aux = min(aux,a[j]);
                if (aux == a[j]) {
                   if (dp[j] + 1 < dp[i] || (dp[j] + 1 == dp[i] && a[who[i]] > a[j])) {
                        dp[i] = dp[j] + 1;
                        who[i] = j;
                   }
                }
            }
        }
        
        if (dp[i] == n + 1) dp[i] = 1;

        if (a[i] == vmin) {
            bstPos = i;
        }
    }
    cout << dp[bstPos] << "\n";
    while (bstPos != who[bstPos]) {
        cout << bstPos << " ";
        bstPos = who[bstPos];
    }
    cout << bstPos;
}

int main()
{
    readData();
    solve();
    return 0;
}