Pagini recente » Cod sursa (job #1389700) | Cod sursa (job #698639) | Cod sursa (job #2055522) | Cod sursa (job #1061715) | Cod sursa (job #938681)
Cod sursa(job #938681)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 5001
#define INF 10000000
int dp[N];
int t[N];
bool ok[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] = INF;
mn = INF;
mn2 = INF;
for (j = i + 1; j <= n; ++j) {
if (mn > a[j] && (a[j] >= a[i])) {
ok[j] = 1;
if ( (dp[i] > dp[j] + 1) || (dp[i] == dp[j] + 1 && a[j] <= mn2))
dp[i] = dp[j] + 1,
t[i] = j,
mn2 = a[j];
}
if (a[j] >= a[i])
mn = min(mn, a[j]);
}
if (dp[i] == INF)
dp[i] = 1;
}
int mx = 0;
int pz = 0;
for (i = 1; i <= n; ++i)
if (!ok[i]) {
if (mx < dp[i]) {
mx = dp[i];
pz = i;
}
else if (mx == dp[i] && a[i] < a[pz]) {
pz = i;
}
}
printf ("%d\n", mx);
for (i = pz; i; i = t[i])
printf ("%d ", i);
printf ("\n");
}