Cod sursa(job #938684)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 13 aprilie 2013 14:36:21
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
#define N 5001
#define INF 10000000
int dp[N];
int t[N];
bool ok[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] = INF;
        mn = INF;
        mn2 = INF;
        for (j = i + 1; j <= n; ++j) {
            if (mn > a[j] && (a[j] >= a[i])) {
                ok[j] = 1;
                if ( (dp[i] > dp[j] + 1) || (dp[i] == dp[j] + 1 && a[j] <= mn2))
                    dp[i] = dp[j] + 1,
                    t[i] = j,
                    mn2 = a[j];
            }
            if (a[j] >= a[i])
                mn = min(mn, a[j]);
        }
        if (dp[i] == INF)
            dp[i] = 1;
    }
     
    int mx = INF;
    int pz = 0;
    for (i = 1; i <= n; ++i)
        if (!ok[i]) {
            if (mx > dp[i]) {
                mx = dp[i];
                pz = i;
            }
            else if (mx == dp[i] && a[i] < a[pz]) {
                pz = i;
            }
        }
    printf ("%d\n", mx);
     
    for (i = pz; i; i = t[i])
        printf ("%d ", i);
    printf ("\n");
}