Pagini recente » Cod sursa (job #725376) | Cod sursa (job #957421) | Cod sursa (job #2322294) | Cod sursa (job #1130455) | Cod sursa (job #2775228)
#include <bits/stdc++.h>
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
const int inf = (int)1e9;
const int maxN = (int)5e3;
int n;
int v[maxN + 5];
int maximalLen[maxN + 5];
int dad[maxN + 5];
int main() {
in >> n;
for (int i = 1; i <= n; i++) {
in >> v[i];
}
/// maximalLen[i] = cel mai scurt subsir crescator maximal
/// care incepe la i
/// maximalLen[i] = min(maximalLen[j] + 1) | j > i, v[j] > v[i]
/// | v[j] = min(v[k]), k = [i, j]
for (int i = n; i >= 1; i--) {
int minValue = inf;
maximalLen[i] = inf;
for (int j = i + 1; j <= n; j++) {
if (v[j] <= minValue && v[j] >= v[i]) {
minValue = v[j];
if (maximalLen[i] > maximalLen[j] + 1) {
maximalLen[i] = maximalLen[j] + 1;
dad[i] = j;
} else if (maximalLen[i] == maximalLen[j] + 1) {
if (v[j] < v[dad[i]]) {
dad[i] = j;
}
}
}
}
if (maximalLen[i] == inf) {
maximalLen[i] = 1;
}
}
int posMaximalLen = 0;
for (int i = 1; i <= n; i++) {
if (maximalLen[posMaximalLen] < maximalLen[i]) {
posMaximalLen = i;
} else if (maximalLen[posMaximalLen] == maximalLen[i] && v[i] < v[posMaximalLen]) {
posMaximalLen = i;
}
}
vector<int> result;
while (posMaximalLen) {
result.push_back(posMaximalLen);
posMaximalLen = dad[posMaximalLen];
}
out << (int)result.size() << "\n";
for (int val : result) {
out << val << " ";
}
return 0;
}