題目的大概意思：有一系列老鼠，每個老鼠有體重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; }
