Pagini recente » Cod sursa (job #1178178) | Cod sursa (job #1566036) | Cod sursa (job #22014) | Cod sursa (job #1721948) | Cod sursa (job #2214637)
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
using namespace std;
ifstream f ("subsir2.in");
ofstream g ("subsir2.out");
int main() {
int n;
f >> n;
vector <int> v(n), len(n, 0), capat(n, 0);
vector <bool> isStart(n, true);
for (int i = 0; i < n; ++i) f >> v[i];
int ans = 1 << 30;
int pos = 0;
for (int i = n - 1; i >= 0; --i) {
int minn = v[i + 1];
len[i] = 1 << 30;
for (int j = i + 1; j < n; ++j) {
if (v[i] <= v[j]) {
if (v[j] < minn) {
minn = v[j];
if (len[j] + 1 < len[i]) {
len[i] = 1 + len[j];
capat[i] = j;
}
}
isStart[j] = false;
}
}
if (len[i] == 1 << 30 && capat[i] == 0) {
len[i] = 1; capat[i] = i;
}
}
for (int i = 0; i < n; ++i) {
if (isStart[i]) {
if (ans > len[i]) {
ans = len[i];
pos = i;
}
}
}
g << ans << '\n' << pos + 1 << ' ';
function <void(int)> reconstr = [&](int pos) {
if (capat[pos] == pos) return;
g << capat[pos] + 1 << ' ';
reconstr(capat[pos]);
};
reconstr (pos);
f.close();
g.close();
return 0;
}