Pagini recente » Cod sursa (job #3256400) | Cod sursa (job #1420421) | Cod sursa (job #649887) | Cod sursa (job #2261966) | Cod sursa (job #501362)
Cod sursa(job #501362)
# include <fstream>
# define DIM 5003
using namespace std;
int n, v[DIM], p[DIM], l[DIM], cpt[DIM];
void read ()
{
ifstream fin ("subsir2.in");
fin>>n;
for(int i=1;i<=n;++i)
fin>>v[i], l[i]=1;
}
void solve ()
{
for(int i=2;i<=n;++i)
for(int j=i-1;j;--j)
if (v[j]<=v[i])
{
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;
}
}
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;
}