Pagini recente » Cod sursa (job #1633262) | Cod sursa (job #1585328) | Cod sursa (job #231320) | Cod sursa (job #633178) | Cod sursa (job #3288959)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
const int LMAX = 5005;
const int INF = 0x3f3f3f3f;
const ll MOD = 1000000007;
//dp[i] --> lungimea subsirului ... pana la pozitia i
int dp[LMAX], v[LMAX], prv[LMAX];
int main() {
int n, i, j, poz;
fin>>n;
for (i = 1; i <= n; i++) {
fin>>v[i];
}
v[0] = -INF;
v[n + 1] = INF;
for (i = n; i >= 0; i--) {
dp[i] = n + 1;
poz = -1;
for (j = i + 1; j <= n + 1; j++) {
if ((poz == - 1 || v[j] < v[poz]) && v[j] >= v[i]) {
if (dp[i] >= dp[j] + 1) {
dp[i] = dp[j] + 1;
prv[i] = j;
}
poz = j;
}
}
}
fout<<dp[0] - 1<<"\n";
i = 0;
vector<int> ans;
while (prv[i] != n + 1) {
ans.push_back(prv[i]);
i = prv[i];
}
for (i = 0; i < ans.size(); i++) {
fout<<ans[i]<<" ";
}
fin.close();
fout.close();
return 0;
}