Pagini recente » Cod sursa (job #964177) | Cod sursa (job #2462311) | Cod sursa (job #2553962) | Borderou de evaluare (job #755263) | Cod sursa (job #3263022)
#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=n;i>=1;i--)
{
dp[i]=1e9+1;
int mn=1e9+1;
for (int j=i+1;j<=n;j++)
{
if (v[j]>=v[i] && v[j]<mn)
{
mn=min (mn, v[j]);
if (dp[j]+1<=dp[i])
{
dp[i]=dp[j]+1;
before[i]=j;
}
}
}
if (dp[i]==1e9+1)
{
dp[i]=1;
before[i]=-1;
}
}
int mn=1e9+1, ans=1e9+1;
for (int i=1;i<=n;i++)
{
if (v[i]<mn)
{
mn=v[i];
ans=min (ans, dp[i]);
}
}
g << ans << "\n";
mn=1e9+1;
for (int i=1;i<=n;i++)
{
if (dp[i]==ans && v[i]<mn)
{
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);
if (crt<vec || vec.size()==0)
{
vec=crt;
vec2=crt2;
}
}
mn=min (mn, v[i]);
}
for (auto nr : vec2)
{
g << nr << " ";
}
return 0;
}