Pagini recente » Cod sursa (job #315662) | Cod sursa (job #2602188) | Cod sursa (job #1439926) | Cod sursa (job #3038026) | Cod sursa (job #1116215)
# include <fstream>
# define maxim 10000001
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int a[5005],ver[5005],lung[5005],urm[5005];
int n,i,j,best,poz,Vmin,minn;
int main()
{
f>>n;
minn=maxim;
best=maxim;
Vmin=maxim;
for (i=1; i<=n; ++i)
{
f>>a[i];
if (minn>a[i]) minn=a[i],ver[i]=1;
}
for (i=n; i>=1; --i)
{
lung[i]=maxim; minn=maxim;
for (j=i+1; j<=n; ++j)
{
if (a[j]>=a[i] && a[j]<minn)
{
minn=a[j];
if (lung[i]>lung[j]+1)
{
lung[i]=lung[j]+1;
urm[i]=j;
}
else if (lung[i]==lung[j]+1 && a[j]<a[urm[i]]) urm[i]=j;
}
}
if (urm[i]==0) lung[i]=1;
if (ver[i]!=0 && lung[i]<best || lung[i]==best && a[i]<Vmin)
{
best=lung[i];
Vmin=a[i];
poz=i;
}
}
g<<lung[poz]<<"\n";
while(poz!=0)
{
g<<poz<<" ";
poz=urm[poz];
}
return 0;
}