Pagini recente » Cod sursa (job #860233) | Cod sursa (job #3042208) | Cod sursa (job #2144286) | Cod sursa (job #1553602) | Cod sursa (job #3263019)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f ("subsir2.in");
ofstream g ("subsir2.out");
int n, v[5005], dp[5005], before[5005];
vector <int> vec, crt, crt2, vec2;
int main()
{
f >> n;
for (int i=1;i<=n;i++)
{
f >> v[i];
}
for (int i=1;i<=n;i++)
{
dp[i]=1e9+1;
int mx=-1e9-1;
for (int j=i-1;j>=1;j--)
{
if (v[j]<=v[i] && v[j]>mx && dp[j]+1<dp[i])
{
dp[i]=dp[j]+1;
before[i]=j;
}
if (v[j]<=v[i])
{
mx=max (mx, v[j]);
}
}
if (dp[i]==1e9+1)
{
dp[i]=1;
before[i]=-1;
}
}
int mx=-1e9-1, ans=1e9+1;
for (int i=n;i>=1;i--)
{
if (v[i]>mx)
{
mx=v[i];
ans=min (ans, dp[i]);
}
}
g << ans << "\n";
mx=-1e9-1;
for (int i=n;i>=1;i--)
{
if (dp[i]==ans && v[i]>mx)
{
crt.clear();
crt2.clear();
int el=i;
while (before[el]!=-1)
{
crt.push_back (v[el]);
crt2.push_back (el);
el=before[el];
}
crt.push_back (v[el]);
crt2.push_back (el);
reverse (crt.begin(), crt.end());
reverse (crt2.begin(), crt2.end());
if (crt<vec || vec.size()==0)
{
vec=crt;
vec2=crt2;
}
}
mx=max (mx, v[i]);
}
for (auto nr : vec2)
{
g << nr << " ";
}
return 0;
}