Pagini recente » Cod sursa (job #678249) | Cod sursa (job #1847867) | Cod sursa (job #1171296) | Cod sursa (job #2188736) | Cod sursa (job #3288957)
#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[n + 1] = INF;
for (i = 1; i <= n + 1; i++) {
dp[i] = n + 1;
poz = -1;
j = i - 1;
while(j > 0) {
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;
}
j--;
}
if (poz == -1) dp[i] = 1, prv[i] = 0;
}
fout<<dp[n + 1]<<"\n";
i = n + 1;
vector<int> ans;
while (prv[i]) {
ans.push_back(prv[i]);
i = prv[i];
}
for (i = ans.size() - 1; i >= 0; i--) {
fout<<ans[i]<<" ";
}
fin.close();
fout.close();
return 0;
}