Pagini recente » Cod sursa (job #1302655) | Cod sursa (job #3270213) | Cod sursa (job #771184) | Cod sursa (job #1601250) | Cod sursa (job #938596)
Cod sursa(job #938596)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 5001
int dp[N];
int t[N];
int n;
int a[N];
int main() {
freopen ("subsir2.in", "r", stdin);
freopen ("subsir2.out", "w", stdout);
scanf ("%d\n", &n);
int i, j, k;
for (i = 1; i <= n; ++i)
scanf ("%d", &a[i]);
dp[n] = 1;
int mn;
int mn2;
for (i = n - 1; i >= 1; --i) {
dp[i] = 0x3f3f3f3f;
mn = 0x3f3f3f3f;
for (j = i + 1; j <= n; ++j) {
if (a[j] < mn && a[j] >= a[i]) {
if (dp[i] > dp[j] + 1)
dp[i] = dp[j] + 1,
t[i] = j,
mn = a[j];
else if (dp[i] == dp[j] + 1 && a[j] < mn)
dp[i] = dp[j] + 1,
t[i] = j,
mn = a[j];
}
if (a[j] >= a[i])
mn = min(mn, a[j]);
}
if (dp[i] == 0x3f3f3f3f)
dp[i] = 1;
}
int mx = 0;
int pz = 0;
for (i = 1; i <= n; ++i)
if (mx < dp[i]) {
mx = dp[i];
pz = i;
}
printf ("%d\n", mx);
for (i = pz; i; i = t[i])
printf ("%d ", i);
printf ("\n");
}