Pagini recente » Cod sursa (job #2487041) | Cod sursa (job #547792) | Cod sursa (job #3140508) | Cod sursa (job #2582760) | Cod sursa (job #1867642)
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[5002], best[5002], last[5002], Next[5002], b[5002], c[5002], first[5002];
int main()
{
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n ; ++i)
scanf("%d", &a[i]);
for(int i = n; i >= 1 ; --i){
int Min = 1000005; best[i] = 1000005;
for(int j = i + 1; j <= n ; ++j){
if(Min > a[j] && a[i] <= a[j]){
Min = a[j];
if(best[i] > best[j] + 1){
best[i] = best[j] + 1;
last[i] = j;
}
else if(best[i] == best[j] + 1 && a[last[i]] > a[j])
last[i] = j;
}
}
if(best[i] == 1000005) best[i] = 1, last[i] = i;
}
int poz = 0, Sol = 2000000000, Min = 1000005, Min2 = 1000005;
for(int i = 1; i <= n ; ++i){
if(Min > a[i] && (best[i] < Sol || (Sol == best[i] && a[i] < Min2))){
Sol = best[i];
poz = i;
Min2 = a[i];
}
if(Min > a[i]) Min = a[i];
}
int tr = poz, NR = 0;
while(tr != last[tr]){
b[++NR] = tr;
tr = last[tr];
}
b[++NR] = tr;
printf("%d\n", Sol);
for(int i = 1; i <= Sol ; ++i)
printf("%d ", b[i]);
return 0;
}