Pagini recente » Cod sursa (job #2070136) | Cod sursa (job #672664) | Cod sursa (job #2784869) | Cod sursa (job #2824564) | Cod sursa (job #381097)
Cod sursa(job #381097)
#include<fstream>
#define inf "subsir2.in"
#define outf "subsir2.out"
#define NMax 5001
#define INF 0x3f3f3f3f
using namespace std;
fstream f(inf,ios::in),g(outf,ios::out);
int N,v[NMax];
int best[NMax],T[NMax];
void Citire()
{
f>>N;
for(int i=1;i<=N;i++)f>>v[i];
}
void Rezolva()
{
int lmin;
int valmin;
int poz;
for(int i=N;i>=1;i--)
{
best[i]=1;
T[i]=i;
valmin=INF;
for(int j=i+1;j<=N;j++)
{
if(v[j]>=v[i] && v[j]<valmin)
{
valmin=v[j];
if(best[j]+1<best[i]){best[i]=best[j]+1;T[i]=j;}
else if(best[j]+1==best[i] && v[j]<v[T[i]])T[i]=j;
}
}
}
int max=0;
for(int i=1;i<=N;i++)
{
if(best[i]>max){max=best[i];poz=i;}
}
g<<max<<"\n";
while(1)
{
g<<poz<<" ";
if(T[poz]==poz)break;
poz=T[poz];
}
}
int main()
{
Citire();
Rezolva();
f.close();
g.close();
return 0;
}