Pagini recente » Cod sursa (job #2738088) | Cod sursa (job #3236439) | Cod sursa (job #3168962) | Cod sursa (job #258479) | Cod sursa (job #3287674)
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int inf = 0x3f3f3f3f;
void solve() {
int n;
cin >> n;
vector <int> v(n + 2), prv(n + 2, 0), dp(n + 2, 0);
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
v[0] = -inf;
v[n + 1] = inf;
for (int i = n; i >= 0; i--) {
dp[i] = inf;
int pozMaxi = -1;
for (int j = i + 1; j <= n + 1; j++) {
if (v[j] < v[i]) {
continue;
}
if (pozMaxi == -1 || v[j] < v[pozMaxi]) {
pozMaxi = j;
if (dp[j] <= dp[i]) {
dp[i] = dp[j];
prv[i] = j;
}
}
}
dp[i]++;
}
cout << dp[0] - 1 << '\n';
vector <int> ans;
int poz = prv[0];
while (poz != n + 1) {
ans.push_back(poz);
poz = prv[poz];
}
for (int x : ans) {
cout << x << ' ';
}
}
signed main() {
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
#endif // LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0);
int nrt = 1;
//cin >> nrt;
while (nrt--) {
solve();
}
return 0;
}