Pagini recente » Cod sursa (job #1669533) | Cod sursa (job #3032973) | Cod sursa (job #2394212) | Cod sursa (job #2402576) | Cod sursa (job #381099)
Cod sursa(job #381099)
#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 valmin;
int poz=1;
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;
}
}
}
g<<best[1]<<"\n";
while(1)
{
g<<poz<<" ";
if(T[poz]==poz)break;
poz=T[poz];
}
}
int main()
{
Citire();
Rezolva();
f.close();
g.close();
return 0;
}