Pagini recente » Cod sursa (job #2854433) | Cod sursa (job #456057) | Cod sursa (job #2624743) | Istoria paginii runda/avram_iancu_1 | Cod sursa (job #1504619)
/*
Solutie O(N^2/2)
pt fiecare i de la N la 1:
pt fiecare j de la i+1 la N:
determin D[i] in functie de D[j];
daca nu am determinat D[i]:
initializez D[i] cu 1;
*/
#include <cstdio>
#include <algorithm>
#define DIM 5010
#define INF 2000000000
using namespace std;
int N, i, position, maxim, D[DIM], V[DIM], T[DIM];
int main ()
{
freopen ("subsir2.in" ,"r", stdin );
freopen ("subsir2.out","w", stdout);
scanf ("%d", &N);
for (int i = 1; i <= N; i ++)
scanf ("%d", &V[i]);
V[0] = -INF;
for (int i = N; i >= 0; i --)
{
int vmin = INF; D[i] = INF;
for (int j = i + 1; j <= N; j ++)
{
if (V[j] < vmin && V[j] >= V[i])
{
vmin = min (vmin, V[j]);
if (D[i] == D[j] + 1 && V[T[i]] > V[j])
T[i] = j;
if (D[i] > D[j] + 1)
{
D[i] = D[j] + 1;
T[i] = j;
}
}
if (V[j] >= V[i] && vmin > V[j])
vmin = V[j];
}
if (D[i] == INF)
{
D[i] = 1;
T[i] = i;
}
}
printf ("%d\n", D[0] - 1);
position = 0;
while (T[position] != position)
{
printf ("%d ", T[position]);
position = T[position];
}
fclose (stdin );
fclose (stdout);
return 0;
}