Pagini recente » fmi-no-stress-7/solutii | Cod sursa (job #141539) | Cod sursa (job #1685552) | Cod sursa (job #2533767) | Cod sursa (job #2857056)
#include <algorithm>
#include <iostream>
using namespace std;
const int NMAX = 5000;
int n, a[NMAX + 1], t[NMAX + 1], dp[NMAX + 1]; //dp[i] = lungimea celui mai scurt scm
inline void afisSol(const int X) {
if(t[X]) afisSol(t[X]);
printf("%d ", X);
}
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]);
int ans = 1;
for(int i = 1; i <= n; ++i) {
dp[i] = 1;
for(int j = i - 1; j; --j) {
if(a[j] <= a[i]) {
dp[i] = dp[j] + 1;
t[i] = j;
break;
}
}
}
int poz = n, maxcrt = 0;
for(int i = n; i; --i) {
if(a[i] > maxcrt && dp[i] < dp[poz])
poz = i;
maxcrt = max(maxcrt, a[i]);
}
printf("%d\n", dp[poz]);
afisSol(poz);
return 0;
}