Pagini recente » Cod sursa (job #1210312) | Cod sursa (job #2452171) | Cod sursa (job #2982836) | Cod sursa (job #1198093) | Cod sursa (job #1458077)
#include <cstdio>
#include <climits>
#include <vector>
using namespace std;
int n , i , j , minn;
vector < int > a , d , nxt;
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d", &n);
a = vector < int > (n + 1); d = vector < int > (n + 1); nxt = vector < int > (n + 1);
for (i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
a[0] = min(a[0] , a[i]);
}
for (i = n; i >= 0; --i)
{
minn = d[i] = INT_MAX;
for (j = i + 1; j <= n; ++j)
if (a[j] >= a[i] && a[j] < minn)
{
minn = a[j];
if (d[i] > d[j] + 1 || (d[i] == d[j] + 1 && a[j] < a[nxt[i]]))
d[i] = d[j] + 1,
nxt[i] = j;
}
if (d[i] == INT_MAX)
d[i] = 1,
nxt[i] = n + 1;
}
printf("%d\n", d[0] - 1);
for (int crt = nxt[0]; crt <= n; crt = nxt[crt])
printf("%d ", crt);
return 0;
}