Pagini recente » Cod sursa (job #563642) | Cod sursa (job #58167) | Cod sursa (job #1014270) | Cod sursa (job #2239319) | Cod sursa (job #1047440)
#include <fstream>
#define Nmax 5005
#define INF 1000000000
using namespace std;
int N,a[Nmax],lis[Nmax],urm[Nmax];
bool bun[Nmax];
inline void Read()
{
int i;
ifstream fin("subsir2.in");
fin>>N;
for(i=1;i<=N;++i)
fin>>a[i];
fin.close();
}
inline void Solve()
{
int minim,poz,x,y,i,j;
bun[1]=true;
minim=a[1];
for(i=2;i<=N;++i)
if(a[i]<minim)
{
bun[i]=true;
minim=a[i];
}
lis[N]=1; urm[N]=0;
for(i=N-1;i>0;--i)
{
x=a[i]; minim=INF; y=INF;
for(j=i+1;j<=N;++j)
if(a[j]>=x && a[j]<y)
{
y=a[j];
if(lis[j]<=minim)
{
minim=lis[j];
poz=j;
}
}
if(minim==INF)
{
lis[i]=1; urm[i]=0;
}
else
{
lis[i]=minim+1;
urm[i]=poz;
}
}
minim=INF;
for(i=1;i<=N;++i)
if(bun[i] && lis[i]<minim)
{
minim=lis[i];
poz=i;
}
ofstream fout("subsir2.out");
fout<<minim<<"\n";
while(poz)
{
fout<<poz<<" ";
poz=urm[poz];
}
fout<<"\n";
fout.close();
}
int main()
{
Read();
Solve();
return 0;
}