Pagini recente » Cod sursa (job #1141426) | Cod sursa (job #2575728) | Cod sursa (job #2410248) | Cod sursa (job #2151647) | Cod sursa (job #3287652)
#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[n + 1] = inf;
for (int i = 1; i <= n + 1; i++) {
dp[i] = inf;
int pozMaxi = -1;
for (int j = i - 1; j >= 0; 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[n + 1] - 1 << '\n';
vector <int> ans;
int poz = prv[n + 1];
while (poz) {
ans.push_back(poz);
poz = prv[poz];
}
reverse(ans.begin(), ans.end());
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;
}