Pagini recente » Cod sursa (job #201922) | Statistici Spiridon Gabriela (Spiridon_Gabriela) | Cod sursa (job #1801376) | Cod sursa (job #2414972) | Cod sursa (job #342953)
Cod sursa(job #342953)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = 5010;
int n;
int a[MAX_N], d[MAX_N], t[MAX_N];
int main()
{
int i, j;
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= n; ++i)
scanf("%d", a + i);
d[n] = 1;
t[n] = n;
for (i = n - 1; i; --i)
{
int k = INF;
d[i] = INF;
for (j = i + 1; j <= n; ++j)
{
if (j > i + 1 && k >= a[j - 1] && a[j - 1] >= a[i])
k = a[j - 1];
if (a[i] <= a[j] && d[j] + 1 <= d[i] && k > a[j])
d[i] = d[j] + 1, t[i] = j;
}
if (d[i] == INF)
d[i] = 1, t[i] = i;
}
int sol = INF, p = 0, mn = INF;
a[0] = INF;
for (i = 1; i <= n; ++i)
{
if ((d[i] < sol || (d[i] == sol && a[i] < a[p])) && a[i] < mn)
sol = d[i], p = i;
if (a[i] < mn)
mn = a[i];
}
printf("%d\n", sol);
for (; t[p] != p; p = t[p])
printf("%d ", p);
printf("%d\n", p);
}