Pagini recente » Cod sursa (job #1767042) | Ciorna | Cod sursa (job #2130135) | Cod sursa (job #1020091) | Cod sursa (job #3289086)
#include <bits/stdc++.h>
#define NMAX 5000
#define LOG 17
#define ll long long int
#define BASE 1024
#define MOD 10000
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int nxt[NMAX+1];
int a[NMAX+1];
int dp[NMAX+1];
int n;
int main()
{
fin >> n;
for(int i=1;i<=n;i++)
{
fin >> a[i];
dp[i] = n+1;
}
a[0] = -2e9;
dp[0] = n+1;
dp[n]=1;
for(int i=n;i>=1;i--)
{
int mx=0;
for(int j=i-1;j>=0;j--)
{
if(a[j] <= a[i] && (!mx || a[mx]<a[j]))
{
mx=j;
if((dp[j]==dp[i]+1 && a[nxt[j]] > a[i]) || (dp[j]>dp[i]+1))
{
dp[j] = dp[i]+1;
nxt[j] = i;
}
}
}
}
fout << dp[0]-1 << '\n';
int j = nxt[0];
while(j)
{
fout << j << " ";
j = nxt[j];
}
}