Pagini recente » Clasament baraj_spiru | Cod sursa (job #3136731) | Cod sursa (job #653412) | Monitorul de evaluare | Cod sursa (job #2631236)
#include <bits/stdc++.h>
#define maxn 5005
std::ifstream fin ("subsir2.in");
std::ofstream fout ("subsir2.out");
int dp[maxn], x[maxn], next[maxn];
bool ok[maxn];
int main()
{
int n, i, j;
fin >> n;
for (i=0; i<n; i++)
fin >> x[i];
dp[n-1] = 1;
for (i=n-2; i>=0; i--){
dp[i] = 1;
for (j=i+1; j<n; j++){
if (x[j] >= x[i]){
ok[j] = true;
if (dp[i] < dp[j] + 1){
dp[i] = dp[j] + 1;
next[i] = j;
}
else if (dp[i] == dp[j] + 1)
if (x[next[i]] > x[j])
next[i] = j;
}
}
}
/*
for (i=0; i<n; i++)
fout << dp[i] << ' ';
fout << '\n';
for (i=0; i<n; i++)
fout << ok[i] << ' ';
*/
int pos = -1, max=1e9;
for (i=0; i<n; i++){
if (ok[i] == false){
if (max > dp[i]){
max = dp[i];
pos = i;
}
else if (max == dp[i] and x[pos] > x[i])
pos = i;
}
}
fout << max << '\n';
fout << pos + 1 << ' ';
while (next[pos] != 0){
pos = next[pos];
fout << pos + 1 << ' ';
}
return 0;
}