Cod sursa(job #739550)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXN 10000
#define INF 2000000000
int A[MAXN], D[MAXN], Next[MAXN], Ok[MAXN];
int sol, last, i, j, poz;
int N;
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&N);
for (i=1; i<=N; ++i)
scanf("%d",&A[i]);
for (i=N; i >= 1; --i){
last = INF; Ok[i] = true; D[i] = INF;
for (j=i+1; j <= N; ++j){
if (A[j] < last && A[i] <= A[j]){
Ok[j] = false;
if (D[i] > D[j] + 1){
D[i] = D[j] + 1;
Next[i] = j;
}
last = A[j];
if (D[j] + 1 == D[i] && A[j] < A[Next[i]]) Next[i] = j;
}
}
if (D[i] == INF) {
D[i] = 1;
Next[i] = 0;
}
}
sol = INF;
for (i=1; i<=N; ++i)
if (Ok[i]){
if (D[i] < sol){
sol = D[i];
poz = i;
}
if (D[i] == sol && A[i] < A[poz])
poz = i;
}
printf("%d\n", sol);
printf("%d", poz);
while (Next[poz]){
poz = Next[poz];
printf(" %d", poz);
}
printf("\n");
return 0;
}