Pagini recente » Cod sursa (job #3173470) | Cod sursa (job #393961) | Cod sursa (job #2947012) | Cod sursa (job #1327289) | Cod sursa (job #340394)
Cod sursa(job #340394)
#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]);
memset(d, INF, sizeof(d));
for (i = n; i; --i)
{
int mn = INF;
for (j = i + 1; j <= n; ++j)
{
if (a[i] < a[j] && a[j] < mn && d[i] == d[j] + 1 && a[j] < a[t[i]])
t[i] = j;
if (a[i] < a[j] && a[j] < mn && d[j] + 1 < d[i])
d[i] = d[j] + 1, t[i] = j;
mn = min(mn, a[j]);
}
if (d[i] == INF)
d[i] = 1, t[i] = i;
}
int mx = 0, p = 0;
for (i = 1; i <= n; ++i)
if (d[i] > mx)
mx = d[i], p = i;
printf("%d\n", mx);
for (; t[p] != p; p = t[p])
printf("%d ", p);
printf("%d\n", p);
}