Pagini recente » Cod sursa (job #2342591) | Cod sursa (job #622573) | Cod sursa (job #216042) | Cod sursa (job #1766212) | Cod sursa (job #1767373)
#include <iostream>
#include<fstream>
using namespace std;
int nxt[5005],best[5005],maxim,minim,mn,minbest,v[5005],i,j,n,poz,minpoz,mx;
int main()
{
ifstream f("subsir2.in");
ofstream g("subsir2.out");
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i];
}
for(i=1;i<=n;i++)
best[i]=(1<<30);
maxim=-(1<<30);
minim=(1<<30);
for(i=n;i>=1;i--)
{
if(v[i]>maxim)
{
maxim=v[i];
best[i]=1;
}
mx=-(1<<30);
for(j=i-1;j>=1;j--)
{
if(v[j]>mx&&v[j]<=v[i])
{
mx=v[j];
if(best[i]+1<best[j]||(best[i]+1==best[j]&&v[i]<v[nxt[j]]))
{
best[j]=best[i]+1;
nxt[j]=i;
}
}
}
}
minbest=(1<<30);minpoz=(1<<30);
for(i=1;i<=n;i++)
{
if(v[i]<minim)
{
minim=v[i];
if(best[i]<minbest)
{
minbest=best[i];
minpoz=i;
poz=i;
}
}
}
g<<minbest<<'\n';
for(i=1;i<=minbest;i++)
{
g<<poz<<' ';
poz=nxt[poz];
}
return 0;
}