Pagini recente » Cod sursa (job #596031) | Istoria paginii utilizator/titus_ticusan | Cod sursa (job #1020945) | Cod sursa (job #594296) | Cod sursa (job #1867568)
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[5002], best[5002], last[5002], Next[5002], b[5002], c[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;
for(int i = 1; i <= n ; ++i){
if(best[i] == 2000000000)best[i] = 1;
int Max = -1000005;
for(int j = i + 1; j <= n ; ++j){
if(a[j] <= a[i]) continue ;
if(Max == -1000005) Max = a[j];
else if(a[j] > Max) continue ;
if(best[i] + 1 <= best[j]){
best[j] = best[i] + 1;
last[j] = i;
Next[i] = 1;
}
}
}
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;
}