Pagini recente » Cod sursa (job #2672644) | Cod sursa (job #1722857) | Cod sursa (job #292395) | Cod sursa (job #632390) | Cod sursa (job #3241864)
#include <fstream>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
#define ll long long
using namespace std;
const int NMAX = 5000;
int d[NMAX + 1];
int v[NMAX + 1];
int urm[NMAX + 1];
ifstream cin("subsir2.in");
ofstream cout("subsir2.out");
void sol(int poz)
{
if (poz == 0)
return ;
sol(urm[poz]);
cout << poz << " ";
}
signed main()
{
int n, i, j;
cin >> n;
for (i = 1; i <= n; i++)
cin >> v[i];
for (i = 1; i <= n; i++)
{
int mn = n + 3;
int mx = -1e7;
for (j = i - 1; j >= 1; j--)
if (v[j] <= v[i] and v[j] > mx)
{
mx = max(mx, v[j]);
if (mn >= 1 + d[j])
{
mn = 1 + d[j];
if (urm[i] == 0 or (v[j] <= v[urm[i]]))
urm[i] = j;
}
}
if (mn == n + 3)
{
mn = 1;
}
d[i] = mn;
}
int mx = -1e7;
int ans = n + 3;
int unde = 0;
for (i = n; i >= 1; i--)
if (v[i] > mx)
{
if (ans >= d[i])
{
ans = d[i];
if (unde == 0 or (v[unde] >= v[i]))
unde = i;
}
mx = v[i];
}
cout << ans << "\n";
sol(unde);
}