Pagini recente » Cod sursa (job #612702) | Cod sursa (job #1712885) | Cod sursa (job #909632) | Cod sursa (job #1378443) | Cod sursa (job #499419)
Cod sursa(job #499419)
#include<fstream>
using namespace std;
ofstream g("subsir2.out");
ifstream f("subsir2.in");
int n,a[5001],bst[5001],t[5001],rez=100000000,poz,minim;
int ok[5001];
void citire()
{
int i;
f>>n;
minim=100000000;
for(i=0;i<n;i++)
{
f>>a[i];
if(minim<=a[i])
continue;
ok[i]=1;
minim=a[i];
}
}
int main()
{
int i,j,minim;
citire();
for(i=n-1;i>=0;i--)
{
bst[i]=minim=100000000;
t[i]=-1;
for(j=i+1;j<n;j++)
{
if(a[j]<a[i])
continue;
if(minim>a[j]&&(bst[i]>bst[j]+1||(bst[i]==bst[j]+1&&a[j]<a[t[i]])))
{
bst[i]=bst[j]+1;
t[i]=j;
}
if(minim>a[j])
minim=a[j];
}
if(bst[i]==100000000)
{
bst[i]=1;
t[i]=i;
}
if(ok[i]&&(rez>bst[i]||(rez=bst[i]&&a[i]<a[poz])))
{
rez=bst[i];
poz=i;
}
}
g<<rez<<"\n";
for(i=poz;i!=t[i];i=t[i])
g<<i+1<<" ";
g<<i+1;
return 0;
}