Cod sursa(job #60306)

Utilizator victorsbVictor Rusu victorsb Data 13 mai 2007 17:48:27
Problema Subsir 2 Scor 79
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 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)
        scrie(last[pos]);
    else
    	return;
    printf("%d ", pos);
}

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

    for (i = 1; i <= n; ++i)
    {
    	max = -1;
        d[i] = INF;
     	for (j = i - 1; j >= 0; --j)
            if (sir[j] <= sir[i] && sir[j] > max)
            {
                if (d[i] > d[j] + 1)
                {
                	d[i] = d[j] + 1;
                    last[i] = j;
                }
                max = sir[j];
            }
    }
    
	max = -1;
    best = n;
    for (i = n - 1; i >= 1; --i)
        if (sir[i] > max)
        {
            if (d[i] < d[best])
            	best = i;
            max = 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;
}