Pagini recente » Cod sursa (job #1089796) | Cod sursa (job #2202620) | Cod sursa (job #2928799) | Cod sursa (job #1512916) | Cod sursa (job #1867608)
#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]), best[i] = 2000000000; first[i] = a[i];}
for(int i = 1; i <= n ; ++i){
if(best[i] == 2000000000) best[i] = 1;
int Min = 1000005;
for(int j = i + 1; j <= n ; ++j){
if(a[j] < a[i]) continue ;
Next[i] = 1;
if(Min == 1000005) Min = a[j];
else if(a[j] >= Min) continue ;
else if(a[j] < Min) Min = a[j];
if(best[i] + 1 < best[j]){
best[j] = best[i] + 1;
last[j] = i;
first[j] = first[i];
}
else if(best[i + 1] == best[j] && first[j] >= first[i]){
last[j] = i;
first[j] = first[i];
}
}
}
int Sol = 2000000000;
for(int i = 1; i <= n ; ++i){
if(best[i] < Sol && Next[i] == 0)
Sol = best[i];
}
int ok = 0;
for(int i = 1; i <= n ; ++i){
if(Sol == best[i] && Next[i] == 0){
if(ok == 0){
int tr = i, NR = 0;
ok = 1;
while(tr){
b[++NR] = tr;
tr = last[tr];
}
}
else{
int tr = i, NR = 0;
while(tr){
c[++NR] = tr;
tr = last[tr];
}
bool k = 0;
for(int i = 1; i <= NR ; ++i){
if(a[b[i]] > a[c[i]]){k = 1; break;}
else if(a[b[i]] < a[c[i]])break;
}
if(k == 1){
for(int i = 1; i <= NR ; ++i)
b[i] = c[i];
}
}
}
}
printf("%d\n", Sol);
for(int i = Sol; i >= 1 ; --i)
printf("%d ", b[i]);
return 0;
}