Pagini recente » Cod sursa (job #576893) | Cod sursa (job #2573058) | Cod sursa (job #2654025) | pregatire_oji_cls_9-10 | Cod sursa (job #830526)
Cod sursa(job #830526)
#include <stdio.h>
int x[5100], dp[5100];
void recon(int idx, int N)
{
printf("%d ", idx);
int j, len = dp[idx] - 1;
if (len == 0)
return ;
int vmin = 1 << 30, where;
for (j = idx; j <= N; j ++)
if (dp[j] == len && x[idx] < x[j])
if (x[j] < vmin)
vmin = x[j], where = j;
recon(where, N);
}
int main()
{
int i, j, N;
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i ++)
scanf("%d", &x[i]);
for (i = N; i >= 1; i --)
{
for (j = i + 1; j <= N; j ++)
if (x[j] > x[i] && dp[j] > dp[i])
dp[i] = dp[j];
dp[i] ++;
}
int sol = 0, idx = 0;
for (i = 1; i <= N; i ++)
if (dp[i] > sol || (dp[i] == sol && x[i] < x[idx]))
sol = dp[i], idx = i;
printf("%d\n", sol);
recon(idx, N);
return 0;
}