Pagini recente » Cod sursa (job #1037845) | Cod sursa (job #1296963) | Cod sursa (job #66543) | Cod sursa (job #1521851) | Cod sursa (job #874883)
Cod sursa(job #874883)
#include <iostream>
#include <fstream>
#include <vector>
#define INF 1<<30
using namespace std;
int n;
bool viz[5005];
int v[5005],next[5005],best[5005];
int main()
{
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i];
for(int i=n;i>=1;i--)
{
int max=INF;
best[i]=INF;
for(int j=i+1;j<=n;j++)
if(v[j]>=v[i] && v[j]<max)
{
viz[j]=true;
if(best[j]+1<best[i] || best[j]+1 == best[i] && v[j]<v[next[i]])
{
best[i]=best[j]+1;
next[i]=j;
}
max=v[j];
}
if(best[i]==INF) best[i]=1;
}
int min=INF,poz=0;
for(int i=1;i<=n;i++)
if(!viz[i]==true && (best[i]<min ||best[i] == min && v[i]<v[poz]))
{
min=best[i];
poz=i;
}
fout<<best[poz]<<'\n';
while(poz)
{
fout<<poz<<" ";
poz=next[poz];
}
return 0;
}