Cod sursa(job #938596)

Utilizator blasterzMircea Dima blasterz Data 12 aprilie 2013 23:30:15
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define N 5001

int dp[N];
int t[N];

int n;
int a[N];

int main() {
    freopen ("subsir2.in", "r", stdin);
    freopen ("subsir2.out", "w", stdout);
    scanf ("%d\n", &n);
    int i, j, k;
    for (i = 1; i <= n; ++i)
        scanf ("%d", &a[i]);

    dp[n] = 1;

    int mn;
    int mn2;
    for (i = n - 1; i >= 1; --i) {
        dp[i] = 0x3f3f3f3f;
        mn = 0x3f3f3f3f;
        for (j = i + 1; j <= n; ++j) {
            if (a[j] < mn && a[j] >= a[i]) {
                if (dp[i] > dp[j] + 1)
                    dp[i] = dp[j] + 1,
                    t[i] = j,
                    mn = a[j];
                else if (dp[i] == dp[j] + 1 && a[j] < mn)
                    dp[i] = dp[j] + 1,
                    t[i] = j,
                    mn = a[j];
            }
            if (a[j] >= a[i])
                mn = min(mn, a[j]);
        }
        if (dp[i] == 0x3f3f3f3f)
            dp[i] = 1;
    }
    
    int mx = 0;
    int pz = 0;
    for (i = 1; i <= n; ++i)
        if (mx < dp[i]) {
            mx = dp[i];
            pz = i;
        }
    printf ("%d\n", mx);
    
    for (i = pz; i; i = t[i])
        printf ("%d ", i);
    printf ("\n");
}