Pagini recente » Cod sursa (job #233386) | Cod sursa (job #993308)
Cod sursa(job #993308)
#include <fstream>
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int Array[5002],N,MinBest[5002],Succ[5002],Use[5002],Can_maximal[5002];
void read()
{
f>>N;
for(int i=1;i<=N;i++)
{
f>>Array[i];
Can_maximal[i]=-1000001;
}
}
void calculate()
{
int i,min=1000001,poz=0,minres=1000001;
MinBest[N]=1;
for(i=N-1;i>=1;i--)
{
min=1000001;
poz=0;
MinBest[i]=1;
for(int j=i+1;j<=N;j++)
{
if(Array[i]<=Array[j] && min==MinBest[j] && Can_maximal[j]<Array[i])
{
if(Array[poz]>Array[j])
poz=j;
}
if(Array[i]<=Array[j] && min>MinBest[j] && Can_maximal[j]<Array[i])
{
MinBest[i]=MinBest[j]+1;
min=MinBest[j];
poz=j;
}
if(Array[i]<=Array[j])
Can_maximal[j]=max(Can_maximal[j],Array[i]);
}
Succ[i]=poz;
}
int start=0;
for(i=1;i<=N;i++)
{
if(Can_maximal[i]==-1000001 && minres==MinBest[i] && Array[start]>Array[i])
start=i;
if(Can_maximal[i]==-1000001 && minres>MinBest[i])
minres=MinBest[i],start=i;
}
g<<minres<<"\n";
for(i=start;i!=0;i=Succ[i])
g<<i<<" ";
g<<"\n";
}
int main()
{
read();
calculate();
return 0;
}