Pagini recente » Cod sursa (job #2849402) | Cod sursa (job #720182) | Cod sursa (job #2414327) | Cod sursa (job #3208038) | Cod sursa (job #499421)
Cod sursa(job #499421)
#include<fstream>
using namespace std;
ofstream g("subsir2.out");
ifstream f("subsir2.in");
int n,a[5001],bst[5001],t[5001],rez=1000001,poz,minim;
int ok[5001];
void citire()
{
int i;
f>>n;
minim=1000001;
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=1000001;
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]==1000001)
{
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;
}