時間限制 10000 ms ・ 記憶體限制 256 MB
題目描述
有一塊 H 列、W 欄的土地。每格以 1 表示可種植，以 0 表示不可種植。你要選出恰好 K 個邊界沿著網格線的非空矩形，每個矩形內都只能包含 1，任兩個矩形不能共用格子，但可以相鄰。
每格種植一單位作物，請求出所選矩形面積總和的最大值。
輸入格式
第一行有 H、W、K；接著 H 行各有 W 個 0 或 1。
- 1 ≤ H、W ≤ 2000
- K 為 1 或 2
- 土地中至少有 K 個值為 1 的格子。
輸出格式
輸出 K 個不重疊矩形可達到的最大面積總和。
來源
TOI 2026 年 6 月潛力組〈作物種植 II〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202606/Plant2.pdf
範例測資
範例輸入 1
3 4 2 1 1 0 1 1 1 0 1 0 1 1 1
範例輸出 1
7
請先登入後再提交程式碼
討論與題解
載入討論區…