Pagini recente » Cod sursa (job #995422) | Cod sursa (job #65954) | Cod sursa (job #2394834) | Cod sursa (job #3281715) | Cod sursa (job #938685)
Cod sursa(job #938685)
#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;
}
mn = INF;
int pz = 0;
for (i = 1; i <= n; ++i)
if (!ok[i]) {
if (mn > dp[i]) {
mn = dp[i];
pz = i;
}
else if (mn == dp[i] && a[i] < a[pz]) {
pz = i;
}
}
printf ("%d\n", mn);
for (i = pz; i; i = t[i])
printf ("%d ", i);
printf ("\n");
}