Pagini recente » Cod sursa (job #2761292) | Cod sursa (job #407495) | Cod sursa (job #1628097) | Cod sursa (job #734724) | Cod sursa (job #1047439)
#include <fstream>
#define Nmax 5005
#define INF 1000000000
using namespace std;
int N,a[Nmax],lis[Nmax],next[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; next[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; next[i]=0;
}
else
{
lis[i]=minim+1;
next[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=next[poz];
}
fout.close();
}
int main()
{
Read();
Solve();
return 0;
}