題目的大概意思：有一系列老鼠，每個(gè)老鼠有體重w以及奔跑的速度s,求這樣一個(gè)最大的序列，使得托福答案
m[i+1].w > m[i].w && m[i+1].s < m[i].s
一開(kāi)始，我用"DAG上的動(dòng)態(tài)規(guī)劃"來(lái)解決這道題目，把每一個(gè)老鼠看成是有向圖中的一個(gè)頂點(diǎn)，有向邊（v1, v2）存在的充要條件是m[v2].w > m[v1].w && m[v2].s < m[v1].s
那題目就轉(zhuǎn)換為求一個(gè)DAG中不確定起點(diǎn)的最長(zhǎng)路徑，用記憶化搜索DP輕松KO,但是我就不知道為啥不能AC（算法復(fù)雜度太高？），如果你知道，告訴我，不勝感激
d[i]表示以i為起點(diǎn)的最長(zhǎng)路徑
dp（i, n）//求解以i為起點(diǎn)的最長(zhǎng)路徑
最后，最長(zhǎng)路徑 = 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;
}

其實(shí)一開(kāi)始我想到的不是DAG,而是將所有老鼠按體重排序，并且體重相同的可以按照速度逆序排，這樣，題目就轉(zhuǎn)換為求解最大遞減子序列，用dp[i]表示以第i個(gè)老鼠（排過(guò)序之后）為起點(diǎn)的最大遞增子序列，狀態(tài)轉(zhuǎn)移方程為
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開(kāi)頭的最大長(zhǎng)度
}
}
cout 《 max 《 endl;
for （int i = 1; i <= max; ++i） {
cout 《 m[flag].id 《 endl;
flag = m[flag].next;
}
return 0;
}