Pagini recente » Cod sursa (job #3217025) | Cod sursa (job #2753467) | Cod sursa (job #30263) | Cod sursa (job #2476547) | Cod sursa (job #2857129)
#include <algorithm>
#include <iostream>
using namespace std;
const int NMAX = 5000;
int n, a[NMAX + 1], t[NMAX + 1], dp[NMAX + 2]; //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]);
for(int i = 1; i <= n; ++i) {
dp[i] = 2e9;
int maxcrt = -2e9;
for(int j = i - 1; j; --j) {
if(a[j] > maxcrt && a[j] <= a[i] &&
(dp[i] > dp[j] + 1 || (dp[i] == dp[j] + 1 && a[t[i]] > a[j]))
) {
dp[i] = dp[j] + 1;
t[i] = j;
}
if(a[j] > maxcrt && a[j] <= a[i]) maxcrt = a[j];
}
if(dp[i] == 2e9) dp[i] = 1;
}
int poz = n + 1, maxcrt = -2e9, mincrt = 2e9;
dp[poz] = 2e9;
for(int i = n; i; --i) {
if(a[i] > maxcrt && (dp[i] < dp[poz] || (dp[i] == dp[poz] && a[i] < mincrt)))
poz = i,
mincrt = a[i];
maxcrt = max(maxcrt, a[i]);
}
printf("%d\n", dp[poz]);
afisSol(poz);
return 0;
}