刪除邊界 題解｜APCS 2019 年 10 月高級 第 4 題

前置知識

這題是「用子矩形當狀態」的動態規劃，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

  • 遞迴＋記憶化（top-down DP）：NTUCPC Guide〈Top down 與 Bottom up〉——先寫出會重算的遞迴，再用表格把算過的答案記下來；吳邦一《AP325》第 6 章的 P-6-21 就是本題（教材 PDF 第 218～221 頁），top-down 與非遞迴兩種寫法都有。
  • 用區間（這題是子矩形）當狀態：NTUCPC Guide〈區間 DP〉——拿掉一步之後，剩下的仍然是同一種形狀的更小問題；文末提到的「用子矩形當狀態」正是本題。
  • 二維陣列：題目的「列」「行」口徑跟 APCS 一樣。

簡潔題意

一個 \(m \times n\) 的 \(0/1\) 矩形，每次選最上、最下、最左或最右的一整條邊界，先把它翻成全 \(0\) 或全 \(1\)（翻一格花費 \(1\)），再把這條邊界整條刪掉。反覆做到整個矩形刪光，求最少翻幾格（\(1 \le m, n \le 25\)）。（APCS 逐筆給分。）

先寫出遞迴：每一步只有四種選擇

不管前面怎麼刪，剩下的永遠是原矩形的一個子矩形：第 \(top\) 到 \(bottom\) 列、第 \(left\) 到 \(right\) 行。所以定義 \(best(top, bottom, left, right)\) ＝ 把這個子矩形刪光的最少翻轉數，答案是 \(best(0, m - 1, 0, n - 1)\)。

一個子矩形的第一步只有四種：刪最上列、最下列、最左行、最右行。刪一條長度 \(L\)、裡面有 \(c\) 個 \(1\) 的邊界，要翻成全同最少翻 \(\min(c, L - c)\) 格；刪掉之後剩下的子矩形又是同一種問題。四種各算「這條邊的翻轉數 \(+\) 剩下子矩形的 \(best\)」，取最小。圖 1 是範例 1 的第一步：四條邊各要翻 \(2, 1, 1, 2\) 格，最省的順序是連刪三次最下列。

圖 1：範例 1 的四條邊各要翻幾格，以及最省的刪除順序（刪最下列三次，共翻 2 格）

只剩一列（或一行）時，可以改成一格一格刪：每條「邊界」只有一格，本來就全同，翻 \(0\) 格。所以 \(top = bottom\) 或 \(left = right\) 時 \(best = 0\)，這是遞迴的終點。

#include <bits/stdc++.h>
using namespace std;

int m, n;
int a[25][25];

int flipCost(int ones, int len) { return min(ones, len - ones); }   // 這條邊要變成全同，最少翻幾格

// 刪光子矩形（第 top ～ bottom 列、第 left ～ right 行）的最少翻轉次數
int best(int top, int bottom, int left, int right) {
    if (top == bottom || left == right) return 0;   // 只剩一列或一行：一格一格刪，免翻轉
    int t = 0, b = 0, l = 0, r = 0;                 // 上、下、左、右四條邊各有幾個 1
    for (int j = left; j <= right; j++) { t += a[top][j]; b += a[bottom][j]; }
    for (int i = top; i <= bottom; i++) { l += a[i][left]; r += a[i][right]; }
    int w = right - left + 1, hgt = bottom - top + 1;
    int ans = flipCost(t, w) + best(top + 1, bottom, left, right);          // 先刪最上列
    ans = min(ans, flipCost(b, w) + best(top, bottom - 1, left, right));    // 先刪最下列
    ans = min(ans, flipCost(l, hgt) + best(top, bottom, left + 1, right));  // 先刪最左行
    ans = min(ans, flipCost(r, hgt) + best(top, bottom, left, right - 1));  // 先刪最右行
    return ans;
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) cin >> a[i][j];
    cout << best(0, m - 1, 0, n - 1) << '\n';
    return 0;
}

這份程式答案是對的，但同一個子矩形會被走到很多次：「先刪上列再刪左行」和「先刪左行再刪上列」到達的是同一個子矩形，卻各算一遍。每層四種選擇，\(m + n - 2\) 層，本站實測 \(10 \times 10\) 的隨機矩形就要 \(13\) 秒，\(25 \times 25\) 跑不完。

加上記憶化就是滿分

子矩形總共只有 \(O(m^2 n^2)\) 個（上下界各 \(O(m)\) 種、左右界各 \(O(n)\) 種），\(25^4 \approx 3.9 \times 10^5\)。開一個四維表格 memo[top][bottom][left][right]，算過的子矩形把答案記下來，下次直接拿，每個子矩形只會真正算一次。每次算要掃四條邊 \(O(m + n)\)，總共約 \(3.9 \times 10^5 \times 50 \approx 2 \times 10^7\) 次加法，本站實測 \(25 \times 25\) 不到 \(0.01\) 秒。

#include <bits/stdc++.h>
using namespace std;

int m, n;
int a[25][25];
int memo[25][25][25][25];                            // -1 ＝ 這個子矩形還沒算過

int flipCost(int ones, int len) { return min(ones, len - ones); }

int best(int top, int bottom, int left, int right) {
    if (top == bottom || left == right) return 0;
    int &ans = memo[top][bottom][left][right];       // 參考：寫 ans 就是寫進表格
    if (ans != -1) return ans;                       // 算過就直接拿
    int t = 0, b = 0, l = 0, r = 0;
    for (int j = left; j <= right; j++) { t += a[top][j]; b += a[bottom][j]; }
    for (int i = top; i <= bottom; i++) { l += a[i][left]; r += a[i][right]; }
    int w = right - left + 1, hgt = bottom - top + 1;
    ans = flipCost(t, w) + best(top + 1, bottom, left, right);
    ans = min(ans, flipCost(b, w) + best(top, bottom - 1, left, right));
    ans = min(ans, flipCost(l, hgt) + best(top, bottom, left + 1, right));
    ans = min(ans, flipCost(r, hgt) + best(top, bottom, left, right - 1));
    return ans;
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) cin >> a[i][j];
    memset(memo, -1, sizeof memo);                   // 全部填 -1
    cout << best(0, m - 1, 0, n - 1) << '\n';
    return 0;
}

跟第一份程式比只多三行：表格、「算過就拿」、「算完記下來」（int &ans 是參考，寫 ans 就是寫進表格）。「還沒算過」的記號要用答案不可能出現的值：答案可以是 \(0\)，所以用 \(-1\)，不能用 \(0\)。

答案最大多少？每條長度 \(L\) 的邊最多翻 \(\lfloor L / 2 \rfloor\) 格，\(25 \times 25\) 的棋盤格把每一條邊都頂到這個上限，答案 \(288\)，int 綽綽有餘。

另一種寫法：由小到大填表

不用遞迴也行：子矩形的 \(best\) 只用到「少一列」或「少一行」的子矩形，所以照高度、寬度由小到大的順序填表，填到某個子矩形時它需要的四個都已經填好。

#include <bits/stdc++.h>
using namespace std;

int m, n;
int a[25][25];
int dp[25][25][25][25];                              // dp[top][bottom][left][right]

int flipCost(int ones, int len) { return min(ones, len - ones); }

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) cin >> a[i][j];
    // 高、寬都從 1 開始放大：算某個子矩形時，少一列或少一行的子矩形都已經算好
    for (int hgt = 1; hgt <= m; hgt++)
        for (int w = 1; w <= n; w++)
            for (int top = 0; top + hgt <= m; top++)
                for (int left = 0; left + w <= n; left++) {
                    int bottom = top + hgt - 1, right = left + w - 1;
                    if (hgt == 1 || w == 1) { dp[top][bottom][left][right] = 0; continue; }
                    int t = 0, b = 0, l = 0, r = 0;
                    for (int j = left; j <= right; j++) { t += a[top][j]; b += a[bottom][j]; }
                    for (int i = top; i <= bottom; i++) { l += a[i][left]; r += a[i][right]; }
                    int ans = flipCost(t, w) + dp[top + 1][bottom][left][right];
                    ans = min(ans, flipCost(b, w) + dp[top][bottom - 1][left][right]);
                    ans = min(ans, flipCost(l, hgt) + dp[top][bottom][left + 1][right]);
                    ans = min(ans, flipCost(r, hgt) + dp[top][bottom][left][right - 1]);
                    dp[top][bottom][left][right] = ans;
                }
    cout << dp[0][m - 1][0][n - 1] << '\n';
    return 0;
}

兩種寫法算的是同一張表，都是滿分；遞迴版只算真正會走到的子矩形，填表版把全部填滿，這題大小差不多。

測過再交：範例沒有「只剩一列」與「非方形的陷阱」

兩個範例都是矩形而且答案很小。沒蓋到：只有一列或一行（直接 \(0\)）、全同（\(0\)）、最大的 \(25 \times 25\) 棋盤格（\(288\)），以及兩種範例會過的錯法——每一步挑當下最便宜的邊、用 \(0\) 當「還沒算過」。

輸入 正確輸出 這一筆在測什麼
1 1 ／ 1 0 一格：不用翻
1 5 ／ 1 0 1 0 1 0 只有一列：一格一格刪，免翻轉
5 1 ／ 1 ／ 0 ／ 1 ／ 0 ／ 1 0 只有一行：同上；把 \(m\)、\(n\) 讀反會讀錯格子
2 2 ／ 0 1 ／ 1 0 1 最小的要翻的矩形：隨便刪一條邊翻 \(1\) 格，剩一列免費
2 3 ／ 0 1 0 ／ 1 0 1 1 刪一列翻 \(1\) 格就剩一列；先刪行反而要 \(2\)；\(m\)、\(n\) 讀反會印 0
3 3 ／ 0 0 1 ／ 0 0 1 ／ 0 1 0 1 每一步挑當下最便宜的邊會印 2：第一步最左行、最上列都免費，但該先刪最右行（翻 \(1\)），之後全免費
3 3 ／ 0 1 0 ／ 1 0 1 ／ 0 1 0 2 棋盤格：四條邊都要翻，刪完一條之後剩下的也是棋盤格
用程式造：\(25 \times 25\) 棋盤格（第 \(i\) 列第 \(j\) 行是 \((i + j) \bmod 2\)） 288 答案最大的一筆：沒有記憶化跑不完
用程式造：\(25 \times 25\) 全是 \(0\) 0 用 \(0\) 當「還沒算過」會超時：每個子矩形的答案都是 \(0\)，表格永遠像沒填過，退回沒有記憶化

九筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 沒有記憶化：兩個範例全過，站上就有提交 \(24 \times 24\) 以上的測資大多超時；本站測資掛 \(10\) 筆。
  • 用 \(0\) 當「還沒算過」：答案是 \(0\) 的子矩形每次都重算，全 \(0\)、全 \(1\) 的 \(25 \times 25\) 測資超時；本站測資掛 \(3\) 筆。記號要用 \(-1\) 這種答案不可能出現的值。
  • 每一步挑當下最便宜的邊：範例 2 印 2；自測表第 6 列印 2。便宜的邊先刪，可能把一條貴的邊留到最後還是得付，四種都要往下算完才知道。
  • 把 \(m\)、\(n\) 讀反：題目第一行是列數 \(m\) 再行數 \(n\)，接下來 \(m\) 列每列 \(n\) 個數；讀反之後範例 2（\(3 \times 5\)）印 2，本站測資掛 \(8\) 筆。
  • 只翻成全 \(0\)，忘了也可以翻成全 \(1\)：一條邊的花費是 \(\min(c, L - c)\) 不是 \(c\)；範例 1 印 4、範例 2 印 2，本站測資掛 \(12\) 筆。