a335. TOI 2024/04 潛力組：切割板材

題目描述

加工廠有一片 R×C 的矩形板材與 N 位買家。每位買家指定板材尺寸及單片收購價，且願意購買任意數量的符合規格板材。

每次切割只能選一片目前的板材，沿水平或垂直方向直線切到底，不能轉彎或中途停止。切割次數不限。板材可以旋轉 90 度，切完後也可以留下沒有賣出的部分。請計算最高總營收。

輸入格式

第一行為正整數 R、C，1 ≤ R, C ≤ 2×10^2。

第二行為正整數 N，1 ≤ N ≤ 10^4。

接著 N 行，每行三個正整數 v、w、h，表示一位買家願以 v 購買一片 w×h 的板材。

• 1 ≤ v ≤ 10^4
• 1 ≤ w ≤ R
• 1 ≤ h ≤ C

原題分組限制：15 分：R = 1 且 C ≤ 10。35 分：R = 1。50 分：無額外限制。

輸出格式

輸出一個整數，表示可獲得的最高營收。

範例 1

輸入：

3 5
4
10 2 2
2 3 1
5 3 4
1 3 1

輸出：

24

範例 2

輸入：

6 6
1
5 1 1

輸出：

180

來源

TOI 2024 年 4 月歷屆題〈切割板材〉，依官方 PDF 重新整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202404/Plate.pdf

標籤：TOI 歷屆