Pagini recente » Cod sursa (job #1061829) | Cod sursa (job #707007) | Cod sursa (job #1098223) | Cod sursa (job #1244967) | Cod sursa (job #501419)
Cod sursa(job #501419)
#include<fstream>
using namespace std;
int v[5009],n,minim;
int l[5009],poz[5009],incepe[5009],solutii[5009],nr,pozitia;
void minimul();
void solve();
int main()
{
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
fin>>n;
int i;
for(i=1;i<=n;i++)
fin>>v[i],l[i]=n,poz[i]=-1;
solve();
minimul();
fout<<minim<<endl;
for(i=pozitia;i>=1;i=poz[i])
fout<<i<<" ";
return 0;
}
void solve()
{
int i,j;
l[n]=1;
for(i=n-1;i>=1;i--)
{
int val=+1000000;
for(j=i+1;j<=n;j++)
if(v[j]>=v[i])
{
if(v[j]<val)
{
if(l[j]+1<l[i])
l[i]=l[j]+1,poz[i]=j;
else
{
if(l[j]+1==l[i] && v[j]<=v[poz[i]])
poz[i]=j;
}
val=v[j];
}
incepe[j]=1;
}
if(l[i]==n)
l[i]=1;
}
}
void minimul()
{
int i,valstart;
minim=n;
for(i=1;i<=n;i++)
if(l[i]<minim && incepe[i]!=1)
minim=l[i],pozitia=i,valstart=v[i];
else
if(l[i]==minim && incepe[i]!=1 && v[i]<valstart)
pozitia=i,valstart=v[i];
}