Cod sursa(job #7623)

Utilizator GabiAlb Gabriel Gabi Data 21 ianuarie 2007 20:29:41
Problema Subsir 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>
#define MAX 5001
#define INF 10000000

int n;
int a[MAX], best[MAX], t[MAX];
int rez = INF;
int poz, minim;
char ok[MAX];

void Read()
{
     freopen("subsir2.in", "r", stdin);
     freopen("subsir2.out", "w", stdout);
     
     int i;
     
     scanf("%d", &n);
     
     minim = INF;
     
     for (i = 0; i < n; i++)
     {
         scanf("%d", a + i);
         
         if (minim <= a[i]) continue;
         ok[i] = 1;
         minim = a[i];
     }
}

int main()
{
    int i, j, minim;
    
    Read();
    
    for (i = n - 1; i >= 0; i--)
    {
        best[i] = minim = INF;
        t[i] = -1;
        for (j = i + 1; j < n; j++)
        {
            if (a[j] < a[i]) continue;
            if (minim > a[j] && (best[i] > best[j] + 1 || (best[i] == best[j] + 1 && a[j] < a[t[i]])))
            {
                best[i] = best[j] + 1;
                t[i] = j;
            }
            if (minim > a[j]) minim = a[j];
        }
        
        if (best[i] == INF)
        {
            best[i] = 1;
            t[i] = i;
        }
        
        if (ok[i] && (rez > best[i] || (rez = best[i] && a[i] < a[poz])))
        {
            rez= best[i];
            poz = i;
        }
    }
    
    printf("%d\n", rez);
    for (i = poz; i != t[i]; i = t[i])
        printf("%d ", i + 1);
    
    printf("%d\n", i + 1);
    return 0;
}