Pagini recente » Cod sursa (job #1672335) | Cod sursa (job #3170454) | Cod sursa (job #897311) | Cod sursa (job #2116538) | Cod sursa (job #2467706)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int v[MAXN], dp[MAXN];
int main()
{
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n;
fin >> n;
for(int i = 1; i <= n; ++i){
fin >> v[i];
dp[i] = 1e9;
}
dp[n] = 1;
for(int i = n - 1; i >= 1; --i){
int mn = 1e9;
for(int j = i + 1; j <= n; ++j){
if(v[i] <= v[j] && v[j] < mn){
mn = v[j];
dp[i] = min(dp[i], dp[j] + 1);
}
}
if(dp[i] == 1e9) dp[i] = 1;
}
int mnval = 1e9, minlen = 1e9;
for(int i = 1; i <= n; ++i){
if(v[i] < mnval){
mnval = v[i];
minlen = min(minlen, dp[i]);
}
}
fout << minlen << "\n";
int pos = 0, last = -1e9;
while(minlen){
int next = 1e9;
for(int i = pos + 1; i <= n; ++i){
if(dp[i] == minlen && last <= v[i] && v[i] < next){
next = v[i];
pos = i;
}
else if(last <= v[i] && v[i] < next) next = v[i];
}
fout << pos << " ";
last = v[pos];
minlen--;
}
return 0;
}