Cod sursa(job #1043139)

Utilizator ELHoriaHoria Cretescu ELHoria Data 28 noiembrie 2013 01:06:36
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 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];

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

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

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

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