Pagini recente » Cod sursa (job #2798438) | Cod sursa (job #1546436) | Cod sursa (job #3177737) | Cod sursa (job #2678577) | Cod sursa (job #2712025)
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
const int NMAX = 5005;
int N, a[NMAX], dp[NMAX], nxt[NMAX];
void min_self(int &a, int b) {
a = min(a, b);
}
int main() {
fin >> N;
for(int i = 1; i <= N; ++i)
fin >> a[i];
for(int i = N; i > 0; --i) {
dp[i] = INF;
bool found = false;
int between = INF;
for(int j = i + 1; j <= N; ++j)
if(a[i] <= a[j] && a[j] < between) {
if(dp[i] > dp[j] + 1) {
dp[i] = dp[j] + 1;
nxt[i] = j;
}
else
if(dp[i] == dp[j] + 1 && a[j] < a[nxt[i]])
nxt[i] = j;
found = true;
between = a[j];
}
if(!found) {
dp[i] = 1;
nxt[i] = -1;
}
}
int between = INF, best = INF, start = 1, prv = INF;
for(int i = 1; i <= N; ++i) {
if(between <= a[i])
continue;
if(dp[i] < best) {
best = dp[i];
start = i;
prv = a[i];
}
else
if(dp[i] == best && a[i] < prv) {
start = i;
prv = a[i];
}
between = a[i];
}
fout << best << '\n';
while(start != -1) {
fout << start << ' ';
start = nxt[start];
}
fout << '\n';
}