Pagini recente » Cod sursa (job #818253) | Cod sursa (job #1533758) | Cod sursa (job #902700) | Cod sursa (job #1143541) | Cod sursa (job #2717387)
#include <bits/stdc++.h>
#define NMAX 5005
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int dp[NMAX], p[NMAX], v[NMAX], b[NMAX];
int main()
{
int n;
fin >> n;
for(int i = 1; i <= n; ++i){
fin >> v[i];
dp[i] = (1 << 30);
}
for(int i = n; i >= 1; --i){
int val = (1 << 30);
for(int j = i + 1; j <= n; ++j){
if(v[i] <= v[j]){
b[j] = 1;
if(v[j] < val){
if(dp[i] >= dp[j] + 1){
dp[i] = dp[j] + 1;
p[i] = j;
}
val = v[j];
}
}
}
if(dp[i] > n)
dp[i] = 1;
}
int rez = 0;
dp[0] = (1 << 30);
for(int i = 1; i <= n; ++i)
if(b[i] == 0 && (dp[rez] > dp[i] || (dp[rez] == dp[i] && v[rez] > v[i])))
rez = i;
fout << dp[rez] << '\n';
for(; rez != 0; rez = p[rez])
fout << rez << ' ';
return 0;
}