Pagini recente » Cod sursa (job #2641798) | Cod sursa (job #1038089) | Cod sursa (job #1021272) | Cod sursa (job #1375540) | Cod sursa (job #340479)
Cod sursa(job #340479)
#include <vector>
#include <fstream>
using namespace std;
#define pb push_back
const int NMAX=5005;
const int Inf=2000000;
int N,x[NMAX],din[NMAX],nxt[NMAX],Sol[NMAX];
vector<int> a,b;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int main()
{
int i,j,k,lmin=Inf,least;
f>>N;
for (i=1;i<=N;++i) f>>x[i];
din[N]=1;
for (i=N-1;i>0;--i)
{
least=Inf;
din[i]=Inf;
for (j=i+1;j<=N;++j)
if (x[j] >= x[i] && least > x[j])
{
least=x[j];
if (din[j]+1 < din[i])
{
din[i]=din[j]+1;
nxt[i]=j;
}
else
if (din[j]+1 == din[i])
if (x[j] < x[nxt[i]])
nxt[i]=j;
}
if (least == Inf) din[i]=1;
}
least=Inf;
for (i=1;i<=N;++i)
if (x[i] < least)
{
least=x[i];
lmin=min(lmin,din[i]);
}
g<<lmin<<'\n';
a.reserve(lmin);
b.reserve(lmin);
a=vector<int>(lmin,Inf);
least=Inf;
for (i=1;i<=N;++i)
if (x[i] < least)
{
least=x[i];
if (lmin == din[i])
{
k=0;
for (j=i;j;j=nxt[j]) b[k++]=x[j];
if (a > b)
{
b=a;
k=0;
for (j=i;j;j=nxt[j]) Sol[++k]=j;
}
}
}
for (i=1;i<=lmin;++i) g<<Sol[i]<<' ';
return 0;
}