题目的大概意思：有一系列老鼠，每个老鼠有体重w以及奔跑的速度s,求这样一个最大的序列，使得托福答案
m[i+1].w > m[i].w && m[i+1].s < m[i].s
一开始，我用"DAG上的动态规划"来解决这道题目，把每一个老鼠看成是有向图中的一个顶点，有向边（v1, v2）存在的充要条件是m[v2].w > m[v1].w && m[v2].s < m[v1].s
那题目就转换为求一个DAG中不确定起点的最长路径，用记忆化搜索DP轻松KO,但是我就不知道为啥不能AC（算法复杂度太高？），如果你知道，告诉我，不胜感激
d[i]表示以i为起点的最长路径
dp（i, n）//求解以i为起点的最长路径
最后，最长路径 = max {dp（i, n）}
[html]
#include <iostream>
using namespace std;
struct Mouse{
int w, s;
Mouse（int _w, int _s）： w（_w）， s（_s） {}
Mouse（）{}
};
Mouse mouse[1001];
int G[1001][1001];
int d[1001];
int dp（int i, int n） {
int& ans = d[i];
if （ans > 0） return ans;
ans = 1;
for （int j = 1; j <= n; j++）
if （G[i][j]） {
int tmp = dp（j, n） + 1;
if （ans < tmp） {
ans = tmp;
}
}
return ans;
}
void print_path（int i, int n） {
cout 《 i 《 endl;
for （int j = 1; j <= n; ++j）
if （G[i][j] && d[i] == d[j] + 1） {
print_path（j, n）；
break;
}
}
int main（） {
int w,s,n = 0;
memset（d, -1, sizeof（d））；
while （scanf（"%d%d", &w, &s） != EOF）
mouse[++n] = Mouse（w, s）；
for （int i = 1; i <= n; ++i） {
for （int j = 1; j <= n; ++j）
if （mouse[j].w > mouse[i].w && mouse[j].s < mouse[i].s）
G[i][j] = 1;
else
G[i][j] = 0;
}
int MAX = 0;
int ans;
for （int i = 1; i <= n; i++）
if （MAX < dp（i, n）） {
MAX = d[i];
ans = i;
}
cout 《 ans 《 endl;
print_path（ans, n）；
return 0;
}

其实一开始我想到的不是DAG,而是将所有老鼠按体重排序，并且体重相同的可以按照速度逆序排，这样，题目就转换为求解最大递减子序列，用dp[i]表示以第i个老鼠（排过序之后）为起点的最大递增子序列，状态转移方程为
dp[i] = max {dp[j]}+1 && （m[j].w > m[i].w && m[j].s < m[i].s 表示j可以接在j前面 ） j = i+1, … n
最后，放出AC代码
[html]
#include <iostream>
using namespace std;
struct Mouse{
int w, s, id, next;
Mouse（int _w, int _s）： w（_w）， s（_s）， next（-1） {}
Mouse（）{}
};
Mouse m[1001];
int dp[1001];
int cmp（const void *a, const void *b） {
if （（（Mouse*）a）->w == （（Mouse*）b）->w）
return （（Mouse*）b）->s - （（Mouse*）a）->s;
else
return （（Mouse*）a）->w - （（Mouse*）b）->w;
}
int main（） {
int w, s, n = 1;
while （cin 》 m[n].w 》 m[n].s）
m[n].id = n++;
--n;
qsort（m+1, n, sizeof（m[1]）， cmp）；
int max = 0;
int flag;
for （int i = n; i >= 1; --i） {
dp[i] = 1;
for （int j = i + 1; j <= n; ++j） {
if （m[j].w > m[i].w && m[j].s < m[i].s）
if （dp[i] < dp[j] + 1） {
dp[i] = dp[j] + 1;
m[i].next = j;
}
}
if （max < dp[i]） {
max = dp[i];
flag = i;
// dp[i]表示以i开头的最大长度
}
}
cout 《 max 《 endl;
for （int i = 1; i <= max; ++i） {
cout 《 m[flag].id 《 endl;
flag = m[flag].next;
}
return 0;
}