Pagini recente » Cod sursa (job #1474692) | Cod sursa (job #1918594) | Cod sursa (job #2266131) | Cod sursa (job #1975824) | Cod sursa (job #1823888)
#include <stdio.h>
#include <algorithm>
using namespace std;
const int Mn = 1e5 + 6;
const int oo = 1 << 30;
int n, ans,mn,poz,sol,minim;
int ar[Mn], dp[Mn], last[Mn];
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &ar[i]);
//ar[0] = -oo;
for (int i = n; i >= 0; i--)
{
mn = oo;
dp[i] = oo;
for (int j = i + 1; j <= n; j++)
if (mn > ar[j] && ar[i] <= ar[j])
{
mn = ar[j];
if (dp[i] > dp[j] + 1)
dp[i] = dp[j] + 1, last[i] = j;
else
if (dp[i] == dp[j] + 1 && ar[last[i]] > ar[j])
last[i] = j;
}
if (dp[i] == oo)
dp[i] = 1, last[i] = i;
}
mn = oo;
poz = -1;
sol = oo;
minim = oo;
for(int i = 1; i <= n; i++)
{
if (mn > ar[i] && (dp[i] < sol || (dp[i] == sol && ar[i] < minim)))
{
sol = dp[i];
mn = ar[i];
poz = i;
minim = ar[i];
//printf("%d\n",i);
}
//printf("%d ",dp[i]);
}
//printf("%d\n", dp[0] - 1);
printf("%d\n",sol);
int it = poz;
printf("%d ",poz);
while (it != last[it])
{
it = last[it];
printf("%d ", it);
}
//printf("\n");
return 0;
}