Pagini recente » Cod sursa (job #1248266) | Cod sursa (job #2525784) | Cod sursa (job #308771) | Cod sursa (job #1840127) | Cod sursa (job #1911655)
#include <fstream>
#define nm 5001
#define INF 1<<30
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n,a[nm],best[nm],t[nm],rez=INF,poz,minn=INF;
bool ok[nm];
void read()
{
int i;
fin>>n;
for(i=1; i<=n; i++)
{
fin>>a[i];
if(a[i]>=minn)
continue;
ok[i]=true;
minn=a[i];
}
fin.close();
}
int main()
{
int i,j;
read();
for(i=n; i>0; i--)
{
best[i]=minn=INF;
t[i]=-1;
for(j=i+1; j<=n; j++)
{
if(a[i]>a[j])
continue;
if(a[j]<minn && (best[i]>best[j]+1 || (best[i]==best[j]+ 1 && a[j]<a[t[i]])))
{
best[i]=best[j]+1;
t[i]=j;
}
if(a[j]<minn)
minn=a[j];
}
if(best[i]==INF)
{
best[i]=1;
t[i]=i;
}
if(ok[i] && (rez>best[i] || (rez==best[i] && a[poz]>a[i])))
{
rez=best[i];
poz=i;
}
}
fout<<rez<<'\n';
for(i=poz; i!=t[i] ; i=t[i])
fout<<i<<' ';
fout<<i;
fout.close();
return 0;
}