題解

卡牌遊戲 (APCS 2023-10 中級)

1.0s 256M

有一個 \(n\) 列、\(m\) 欄的表格，每個格子上都放著一張具有整數數值的 卡牌。每一個在表格中出現的數值都恰好出現兩次。

若兩張數值同為 \(x\) 的卡牌位於同一列或同一欄，而且它們之間沒有任何 尚未移除的卡牌，你就可以移除這兩張卡牌，並獲得 \(x\) 分。移除後的格子 會變成空格；空格不會阻擋其他卡牌。

你可以重複進行以上操作，也可以自行選擇每次要移除的牌對。請求出最多 可以獲得多少分。

輸入格式

第一列包含兩個整數 \(n\)、\(m\)，分別表示表格的列數與欄數。

接下來 \(n\) 列，每列包含 \(m\) 個整數，表示表格中的卡牌數值。

限制

  • \(1\le n\le20\)
  • \(1\le m\le40\)
  • 每張卡牌的數值介於 \(0\) 到 \(1000\) 之間
  • 每一個出現的數值都恰好出現兩次
  • \(nm\) 為偶數

輸出格式

輸出一個整數，表示可以獲得的最大總分。

評分說明

每一筆測試資料的執行時間限制均為 \(1\) 秒，依正確通過的測試資料筆數給分。其中：

子題 分數 額外限制
1 60 \(n=1\)
2 40 無額外限制

範例輸入 1

1 8
0 2 3 3 0 2 5 5

範例輸出 1

8

範例解釋 1

數值為 3 與 5 的兩組卡牌都可以移除，因此最多得到 \(3+5=8\) 分。

範例輸入 2

3 6
0 2 3 8 0 2
1 1 4 4 5 7
5 6 3 8 6 7

範例輸出 2

29

範例解釋 2

可以依序移除數值為 1、4、7、3、8、6 的牌對，總分為 \(1+4+7+3+8+6=29\)。

題目來源

APCS 2023 年 10 月實作題第 2 題「卡牌遊戲」

題目頁說明

快速鍵

主要功能

  • 範例測試 — 執行題目附帶的範例測資並自動比對預期輸出。
  • 自訂測試 — 自己貼 stdin 執行程式。可勾選「與預期輸出比對 (diff)」做行對行比對。
  • 模板 — 貼上你在個人資料設定的預設程式碼模板。
  • 協作 — 與其他同學共筆編輯這題的程式碼。
  • 自動草稿 — 編輯器內容每 1.5 秒自動存到瀏覽器（per 帳號 / 題目 / 語言）。
  • 提交 — 把程式碼交給 judge 評測，回傳 AC / WA / TLE 等結果。

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB （約 100 萬字元）
  • 自訂測試與範例測試共用一個沙箱，每人約 3 秒 1 次 （範例測試 1 秒 1 次）
  • 自訂測試與範例測試都有 15 秒 牆鐘上限（正式評測仍依題目原本時限）
  • 互動題不提供自訂測試（無法模擬與 judge 互動）。
  • 提交評測本身沒有 rate limit，但同題短時間內多次提交會被視為刷分。