本题就先排序老鼠的重量，然后查找老鼠的速度的最长递增子序列，只是由于须要按原来的标号输出，故此须要使用struct把三个信息打包起来。
查找最长递增子序列使用动态规划法。主要的一维动态规划法了。
记录路径：仅仅须要记录后继标号，就能够逐个输出了。
#include <stdio.h>
#include <algorithm>
using namespace std; const int MAX_N = 1005; struct MouseSpeed
{
int id, w, s;
bool operator<(const MouseSpeed &ms) const
{
return w < ms.w;
}
}; int N;
MouseSpeed msd[MAX_N];
int post[MAX_N], tbl[MAX_N]; int main()
{
N = 0;
while (~scanf("%d %d", &msd[N].w, &msd[N].s))
{
msd[N].id = N+1;
++N;
} sort(msd, msd+N); //fullfill condition 1: weight increase
fill(tbl, tbl+N, 1);//initialize dynamic table post[N-1] = N-1;
for (int i = N-2; i >= 0; i--)
{
post[i] = i; //as the print out terminate term
for (int j = i+1; j < N; j++)
{
if (msd[i].s>msd[j].s && msd[i].w!=msd[j].w && tbl[i]<tbl[j]+1)
{//strictly increase, so don't forget msd[i].w must < msd[j].w
tbl[i] = tbl[j]+1;//update longest subsequence
post[i] = j;//record the post
}
}
} int id = 0, maxSeq = 0;
for (int i = 0; i < N; i++)//find the max sequence starting point
{
if (maxSeq < tbl[i])
{
id = i;
maxSeq = tbl[i];
}
} printf("%d\n", maxSeq);
printf("%d\n", msd[id].id);
while (id != post[id])
{
id = post[id];
printf("%d\n", msd[id].id);//print out the original indices
} return 0;
}