Pagini recente » Profil andrici_cezar | Cod sursa (job #2224339) | Cod sursa (job #751731) | Cod sursa (job #1222769) | Cod sursa (job #2697848)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("subsir2.in");
ofstream fout("subsir2.out");
const int nmax = 5000 + 50;
int n, a[nmax], dp[nmax], rez[nmax];
bool marked[nmax];
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> a[i];
}
for (int i = 1; i <= n; ++i) {
bool ok = false;
marked[i] = true;
int nr, pos = 0;
for (int j = i - 1; j >= 1; j --) {
if (!ok) {
if (a[j] <= a[i]) {
dp[i] = dp[j];
nr = a[j];
pos = j;
ok = true;
}
}
else {
if (a[j] <= a[i] && a[j] >= nr) {
if (dp[j] < dp[i]) {
dp[i] = dp[j];
marked[pos] = true;
nr = dp[j];
pos = j;
}
}
}
marked[pos] = false;
}
dp[i] ++;
}
int mini = INT_MAX, pos = 0;
for (int i = 1; i <= n; ++ i) {
if (marked[i] && dp[i] <= mini) {
mini = dp[i];
pos = i;
}
}
fout << mini << '\n';
int k = 0, nr = a[pos];
for (int i = pos; i >= 1; --i) {
if (dp[i] == mini && a[pos] >= a[i]) {
rez[++k] = i;
mini --;
}
}
for (int i = k; i >= 1; --i)
fout << rez[i] << ' ';
return 0;
}