Cod sursa(job #938675)

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