Pagini recente » Cod sursa (job #2710928) | Cod sursa (job #1053179) | Cod sursa (job #1111869) | Istoria paginii runda/very.easy | Cod sursa (job #813399)
Cod sursa(job #813399)
#include<fstream>
#include<cmath>
using namespace std;
int n,v[5010],sol=2000000000,ind;
int best[5010],next[5010];
bool pred[5010];
int main()
{
int i,j,minim;
ifstream fin("subsir2.in");
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i];
fin.close();
v[0]=2000000000;
for(i=n;i>0;i--)
{
best[i]=2000000000;
minim=2000000000;
for(j=i+1;j<=n;j++)
{
if(v[j]>=v[i] && v[j]<minim)
{
if(best[i]>best[j]+1 || (best[i]==best[j]+1 && v[j]<v[next[i]]))
{
best[i]=best[j]+1;
next[i]=j;
pred[j]=true;
}
minim=v[j];
}
}
if(best[i]==2000000000)
best[i]=1;
}
for(i=1;i<=n;i++)
{
if(!pred[i] && best[i]<sol)
{
sol=best[i];
ind=i;
}
}
ofstream fout("subsir2.out");
fout<<sol<<"\n";
while(ind)
{
fout<<ind<<' ';
ind=next[ind];
}
fout<<"\n";
fout.close();
return 0;
}