Pagini recente » Profil catalinaionela77 | Cod sursa (job #1464411)
# include <bits/stdc++.h>
using namespace std;
ifstream fi("subsir2.in");
ofstream fo("subsir2.out");
const int nmax = 5005;
const int inf = 2e9;
int dp[nmax];
int pr[nmax];
int s[nmax];
int main(void)
{
int n;
fi>>n;
for (int i = 1;i <= n;++i) fi>>s[i];
s[0] = -inf;
for (int i = n;i+1;--i)
{
dp[i] = inf;
pr[i] = i;
int mn = inf;
for (int j = i + 1;j <= n;++j)
if (mn > s[j] && s[i] <= s[j])
{
mn = s[j];
if (dp[j] + 1 < dp[i]) dp[i] = dp[j] + 1,pr[i] = j;
else
if (dp[j] + 1 == dp[i] && s[j] < s[pr[i]]) pr[i] = j;
}
if (dp[i] == inf) dp[i] = 1;
}
//for (int i = 0;i <= n;++i) cout << pr[i] << ' ';cout << '\n';
fo << dp[0] - 1 << '\n';
int p = 0;
while (pr[p] != p)
{
p = pr[p];
fo << p << ' ';
}
return fo << '\n',0;
}