Pagini recente » Cod sursa (job #1908628) | Cod sursa (job #2493831) | Cod sursa (job #2986337) | Cod sursa (job #1570185) | Cod sursa (job #1500726)
#include<iostream>
#include<fstream>
#include<bitset>
using namespace std;
const int NMAX=5005;
const int inf=10000000;
int v[NMAX],lg[NMAX],suc[NMAX];
bitset<NMAX> extins;
int main()
{
ifstream si;
si.open("subsir2.in");
ofstream so;
so.open("subsir2.out");
int n;
si>>n;
int i;
for(i=1;i<=n;++i)
si>>v[i];
int j,k;
for(i=n;i>0;--i)
{
k=inf;
lg[i]=inf;
for(j=i+1;j<=n;++j)
{
if(k>=v[j]&&v[i]<=v[j])
{
extins[j]=1;
k=v[j];
if(lg[j]+1<lg[i])
{
lg[i]=lg[j]+1;
suc[i]=j;
}
else
if(lg[j]+1==lg[i])
if(v[suc[i]]>v[j])
suc[i]=j;
}
}
if(k==inf)
lg[i]=1;
}/*
for(i=1;i<=n;++i)
cout<<v[i]<<' ';
cout<<'\n';
for(i=1;i<=n;++i)
cout<<lg[i]<<' ';
cout<<'\n';
for(i=1;i<=n;++i)
cout<<v[suc[i]]<<' ';
cout<<'\n';
for(i=1;i<=n;++i)
cout<<extins[i]<<' ';
cout<<'\n';
*/int minn=inf+3,poz=0;
for(i=1;i<=n;i++)
{
if(!extins[i])
{
if(minn>lg[i])
{
minn=lg[i];
poz=i;
}
else
{
if(minn==lg[i])
{
if(v[i]<v[poz])
poz=i;
}
}
}
}
so<<minn<<'\n';
while(poz)
{
so<<poz<<' ';
poz=suc[poz];
}
so<<'\n';
return 0;
}