字母配對 題解|APCS 2025 年 11 月高級 第 1 題
前置知識
這題的滿分做法是記憶化搜尋,下面的講解直接把它當成已知,沒讀過的先讀:
- 記憶化搜尋(top-down DP):NTUCPC Guide〈Top-down 與 Bottom-up〉——遞迴把「從這個狀態開始最多拿幾分」算出來後存起來,同一個狀態第二次問直接查表。吳邦一《AP325》第 6 章「動態規劃」也有完整講解(Python 版各章索引)。
簡潔題意
有 \(k\) 疊卡片,每張有一個大寫字母與一個分數。一次操作取走不同兩疊的頂牌,兩張字母要相同,得到兩張分數的和。可以操作零次或多次,求最高總分(\(2 \le k \le 6\),每疊 \(0 \sim 12\) 張,分數是 \(1 \sim 10\) 的整數)。
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(30\) 分):\(k = 3\)。
- 子題組 2(\(70\) 分):無額外限制。
狀態只跟「每疊拿走幾張」有關
每疊只能從頂端往下拿,所以不管前面是怎麼配對的,只要知道每一疊目前拿走了幾張,接下來能做的事就完全一樣。把這 \(k\) 個數字合起來當成一個狀態:第 \(i\) 疊有 \(n_i + 1\) 種進度,狀態總數是 \((n_1 + 1)(n_2 + 1) \cdots (n_k + 1)\),最多 \(13^6 \approx 4.8 \times 10^6\) 種。
從某個狀態出發最多還能拿幾分,記成 best_from(state):
- 枚舉任兩疊 \(i < j\),兩疊都還有牌、而且頂牌字母相同,就可以拿:得分是兩張的分數和,再加上「兩疊各往下一張」那個狀態的
best_from。 - 所有合法的拿法取最大值;一種都拿不了(或不想再拿)就是 \(0\)。
每個狀態最多枚舉 \(\binom{6}{2} = 15\) 種配對,總共約 \(7 \times 10^7\) 次,但同一個狀態一定要只算一次——用陣列把算過的答案存起來(記憶化)。不存的話每個狀態會被走到非常多次,會超時。
先拿下 30 分:三疊就用三維陣列
子題組 1 的 \(k = 3\),三疊的進度就是三個數字,直接開 memo[13][13][13],三種配對(\(1\)–\(2\)、\(1\)–\(3\)、\(2\)–\(3\))各寫一行。
#include <iostream>
#include <algorithm>
using namespace std;
// 子題組 1:固定 k = 3,直接用三維陣列記錄「三疊各拿走了幾張」
int cnt[3];
char letter[3][12];
int score[3][12];
int memo[13][13][13]; // -1 表示還沒算過
int best_from(int a, int b, int c) {
if (memo[a][b][c] != -1) return memo[a][b][c];
int best = 0;
// 第 1、2 疊配對
if (a < cnt[0] && b < cnt[1] && letter[0][a] == letter[1][b])
best = max(best, score[0][a] + score[1][b] + best_from(a + 1, b + 1, c));
// 第 1、3 疊配對
if (a < cnt[0] && c < cnt[2] && letter[0][a] == letter[2][c])
best = max(best, score[0][a] + score[2][c] + best_from(a + 1, b, c + 1));
// 第 2、3 疊配對
if (b < cnt[1] && c < cnt[2] && letter[1][b] == letter[2][c])
best = max(best, score[1][b] + score[2][c] + best_from(a, b + 1, c + 1));
return memo[a][b][c] = best;
}
int main() {
int k;
cin >> k; // 子題組 1 保證 k = 3
for (int i = 0; i < 3; i++) {
cin >> cnt[i];
for (int j = 0; j < cnt[i]; j++) cin >> letter[i][j] >> score[i][j];
}
for (int a = 0; a < 13; a++)
for (int b = 0; b < 13; b++)
for (int c = 0; c < 13; c++) memo[a][b][c] = -1;
cout << best_from(0, 0, 0) << '\n';
return 0;
}
兩個範例都是 \(k = 3\),這個版本兩個都會過;子題組 1 的測資全對,穩拿 \(30\) 分。
從 30 分到 100 分:把每疊的進度編成一個整數
\(k\) 不固定就不能寫死幾維。把進度「混合進位」成一個整數:第 \(i\) 疊的進度每加 \(1\),編號就加 weight[i],其中 weight[i] 等於前面各疊 \((n_j + 1)\) 的乘積(就像十進位的個位、十位、百位,只是每一位的進位數不同)。拿走第 \(i\)、\(j\) 疊的頂牌,新狀態的編號就是 state + weight[i] + weight[j],記憶體開一個長度為狀態總數的陣列即可(最多 \(4.8 \times 10^6\) 個 int,約 19 MB)。
實測最壞的情況(\(6\) 疊各 \(12\) 張、字母全部相同)約 \(0.4\) 秒,時限 \(2\) 秒。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int k;
int cnt[6]; // 每疊的張數
char letter[6][12]; // letter[i][j]:第 i 疊由頂往下第 j 張的字母
int score[6][12]; // score[i][j]:對應的分數
int taken[6]; // taken[i]:第 i 疊目前已經拿走幾張(=頂牌的索引)
int weight[6]; // 混合進位:第 i 疊的 taken 每加 1,狀態編號加 weight[i]
vector<int> memo; // memo[state]:從這個狀態開始最多還能拿幾分,-1 表示還沒算
int best_from(int state) {
if (memo[state] != -1) return memo[state];
int best = 0; // 不再操作也可以,至少是 0 分
for (int i = 0; i < k; i++) {
if (taken[i] == cnt[i]) continue; // 第 i 疊已經空了
for (int j = i + 1; j < k; j++) {
if (taken[j] == cnt[j]) continue;
if (letter[i][taken[i]] != letter[j][taken[j]]) continue; // 頂牌字母不同
int gain = score[i][taken[i]] + score[j][taken[j]];
taken[i]++;
taken[j]++;
best = max(best, gain + best_from(state + weight[i] + weight[j]));
taken[i]--;
taken[j]--;
}
}
return memo[state] = best;
}
int main() {
cin >> k;
int states = 1; // 狀態總數 = (n_1 + 1)(n_2 + 1)...(n_k + 1)
for (int i = 0; i < k; i++) {
cin >> cnt[i];
weight[i] = states;
states *= cnt[i] + 1;
for (int j = 0; j < cnt[i]; j++) cin >> letter[i][j] >> score[i][j];
}
memo.assign(states, -1);
cout << best_from(0) << '\n';
return 0;
}
測過再交:兩個範例都只有三疊
範例都是 \(k = 3\)、每疊都有牌,答案是 \(7\) 和 \(0\)。沒蓋到的:只有兩疊、有空的疊、疊數到 \(6\),還有最花時間的大輸入。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
2 / 0 / 2 A 5 A 7 |
0 |
只有兩疊、其中一疊是空的:同一疊的兩張不能配 |
4 / 0 / 1 A 1 / 0 / 1 A 9 |
10 |
空的疊夾在中間:混合進位裡那一位只有 \(n_i + 1 = 1\) 種進度 |
6 / 1 A 1 / 1 A 2 / 1 A 3 / 1 A 4 / 1 A 5 / 1 A 6 |
21 |
疊數到 \(6\):六張兩兩配成三對、全部拿走(子題組 1 版只讀了前三疊,印 5) |
用程式造:\(6\) 疊各 \(12\) 張,全部是 A 10 |
720 |
最壞的輸入:任兩疊的頂牌都能配,要走的狀態最多 |
四筆都親眼看過正確,這題就穩了。
常犯錯誤
- 每次先拿分數最高的那一對:眼前分數高的配對可能擋掉後面更好的。範例 1 就會印
6。 - 權重乘 \(n_i\) 而不是 \(n_i + 1\)(每疊的進度是拿走 \(0 \sim n_i\) 張,共 \(n_i + 1\) 種):陣列開得太小,範例 1 就會印錯;有空的疊時(自測表第 2 列)狀態總數變成 \(0\),程式直接當掉。
- 沒有記憶化,直接遞迴枚舉每一種拿法:範例全過;自測表第 4 列跑超過 \(10\) 秒,本站 \(20\) 筆有 \(7\) 筆超時。
- 用
map<vector<int>, int>存記憶化:寫起來省事,但每次查表都要比對整個vector。自測表第 4 列要跑約 \(10\) 秒、記憶體也超過 \(256\) MB;換成混合進位編碼配陣列只要 \(0.4\) 秒。