Cod sursa(job #917642)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 10:59:58
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<iostream>
#include<cstdio>
#define INF 0x3f3f3f3f
#define maxn 5005
using namespace std;
int x[maxn],L[maxn],poz[maxn],n,i,j,Min,ante,val,Minim,st;
bool check[maxn];
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for(i=1; i<=n; ++i)
scanf("%d",&x[i]);
for(i=n; i>=1 ; --i)
{
L[i]=1;
poz[i]=i;
check[i]=true;
Minim=INF;
Min=INF;
for(j=i+1; j<=n; ++j)
{
if(x[i]<=x[j])
{
if(L[j]<Minim && x[j]<Min)
{
Minim=L[j];
poz[i]=j;
L[i]=L[j]+1;
}
else
if(L[j]==Minim && x[j]<Min && x[j]<=x[poz[i]])
poz[i]=j;
if(x[j]<Min)
Min=x[j];
check[j]=false;
}
}
}
Minim=INF;
for(i=1; i<=n; ++i)
if(check[i]==true)
{
if(L[i]<Minim)
{
Minim=L[i];
st=i;
}
else
if(L[i]==Minim && x[st]>x[i])
st=i;
}
printf("%d\n%d ",L[st],st);
while(poz[st]!=st)
{
printf("%d ",poz[st]);
st=poz[st];
}
return 0;