Pagini recente » Cod sursa (job #1002697) | Istoria paginii runda/idulrundei | Cod sursa (job #2042009) | Cod sursa (job #1109389) | Cod sursa (job #501370)
Cod sursa(job #501370)
# include <fstream>
# define DIM 5003
using namespace std;
int n, v[DIM], p[DIM], l[DIM], cpt[DIM], poz[DIM];
void read ()
{
ifstream fin ("subsir2.in");
fin>>n;
for(int i=1;i<=n;++i)
fin>>v[i], l[i]=DIM;
}
void solve ()
{
int val;
l[1]=1;
for(int i=2;i<=n;++i)
{
val=-2000000;
for(int j=i-1;j;--j)
{
if (v[j]<=v[i] && v[j]>val)
{
if (l[j]+1<l[i])
l[i]=l[j]+1, p[i]=j, cpt[j]=1;
else
if (l[j]+1==l[i] && v[j]<v[p[i]])
p[i]=j, cpt[j]=1;
}
if(val==-2000000)
{
if (v[j]<v[i])
val=v[j];
}
else if (v[j]<val)
val=v[j];
}
if (l[i]==DIM)
l[i]=1;
}
}
void write ()
{
int uv=2000000, up=n+1, sol[DIM], lmin=DIM;
for(int i=n;i;--i)
if (!cpt[i])
{
if (l[i]<lmin)
lmin=l[i], uv=v[i], up=i;
else if (l[i]==lmin && uv>v[i])
uv=v[i], up=i;
}
sol[0]=0;
do {
sol[++sol[0]]=up;
up=p[up];
}
while (up);
freopen("subsir2.out", "w", stdout);
printf("%d\n", sol[0]);
for(int i=sol[0];i;--i)
printf("%d ", sol[i]);
}
int main ()
{
read ();
solve ();
write ();
return 0;
}