Pagini recente » Cod sursa (job #2961919) | Profil StarGold2 | Cod sursa (job #148129) | Cod sursa (job #2838445) | Cod sursa (job #872879)
Cod sursa(job #872879)
#include <cstdio>
#include <fstream>
using namespace std;
const int N = 5001 ;
int n,R,A[N],P[N],L[N];
bool C[N];
void READ ()
{
ifstream in ("subsir2.in");
in>>n;
for( int i=1 ; i<=n ; ++i )
{
in>>A[i];
L[i]=N;
}
}
void SOLVE ()
{
L[n]=1;
for(int i=n-1;i;--i)
{
int V=1<<30;
for(int j=i+1;j<=n;++j)
if(A[i]<=A[j])
{
if(A[j]<V)
{
if(L[j]+1<L[i])
{
L[i]=L[j]+1;
P[i]=j;
}
else
if(L[j]+1==L[i]&&A[j]<A[P[i]])
P[i]=j;
V=A[j];
}
C[j]=1;
}
if(L[i]==N)
L[i]=1;
}
int V,Lm=N;
for(int i=1;i<=n;++i)
{
if(C[i])
continue;
if(L[i]<Lm)
{
Lm=L[i];
V=A[i];
R=i;
}
else
if(L[i]==Lm&&A[i]<V)
{
V=A[i];
R=i;
}
}
}
void OUT ()
{
freopen ("subsir2.out","w",stdout);
printf("%d\n",L[R]);
for(;R;R=P[R])
printf("%d ",R);
}
int main ()
{
READ ();
SOLVE ();
OUT ();
return 0;
}