Pagini recente » Cod sursa (job #510851) | Cod sursa (job #1202512) | Cod sursa (job #1983586) | Cod sursa (job #3120986) | Cod sursa (job #2202218)
#include<fstream>
using namespace std;
ifstream fi("subsir2.in");
ofstream fo("subsir2.out");
int n,i,j,k,Dp[5005],A[5005],Rec[5005],rez,ind,minim;
int main()
{
fi>>n;
for(i=1; i<=n; i++)
fi>>A[i];
Dp[n]=1;
Rec[n]=n+1;
for(i=n-1; i>=1; i--)
{
k=1000000000;
Dp[i]=1000000000;
Rec[i]=n+1;
for(j=i+1; j<=n; j++)
{
if(A[j]>=A[i] && A[j]<k)
{
if(Dp[j]+1<Dp[i])
{
Dp[i]=Dp[j]+1;
Rec[i]=j;
}
else
if(Dp[j]+1==Dp[i] && A[j]<A[Rec[i]])
Rec[i]=j;
}
if(A[j]>=A[i])
k=min(k,A[j]);
}
if(Dp[i]==1000000000)
Dp[i]=1;
}
minim=rez=1000000000;
for(i=1; i<=n; i++)
{
if(A[i]<minim)
{
minim=A[i];
if(rez>Dp[i])
{
rez=Dp[i];
ind=i;
}
}
}
fo<<rez<<"\n";
while(ind!=n+1)
{
fo<<ind<<" ";
ind=Rec[ind];
}
fi.close();
fo.close();
return 0;
}