Cod sursa(job #60313)

Utilizator victorsbVictor Rusu victorsb Data 13 mai 2007 18:03:47
Problema Subsir 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>

#define Nmax 5005
#define INF 0x3f3f3f3f

int n;
int sir[Nmax], d[Nmax], last[Nmax];

void citire()
{
	int i;
    
 	scanf("%d\n", &n);
    for (i = 1; i <= n; ++i)
    	scanf("%d ", &sir[i]);
}

void scrie(int pos)
{
	if (pos != n + 1)
    {
    	printf("%d ", pos);
        scrie(last[pos]);
    }
    else
    	return;
}

void solve()
{
    int i, j, min, best;

    sir[n + 1] = INF - 1;
    for (i = n; i >= 1; --i)
    {
    	min = INF;
        d[i] = INF;
     	for (j = i + 1; j <= n + 1; ++j)
            if (sir[j] >= sir[i] && sir[j] < min)
            {
                if (d[i] >= d[j] + 1)
                {
                	d[i] = d[j] + 1;
                    last[i] = j;
                }
                min = sir[j];
            }
    }
    
	min = INF;
    best = 1;
    for (i = 1; i <= n; ++i)
        if (sir[i] < min)
        {
            if (d[i] >= d[best])
            	best = i;
            min = sir[i];
        }

    printf("%d\n", d[best]);
    scrie(best);
}

int main()
{
	freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);
    citire();
    solve();
    return 0;
}