[題解] TIOJ 2173 收集寶藏 (北市賽 2019 pE)

題意

兩個人到一個 $n\times m$ 大的迷宮裡探險
在迷宮裡只能往右和往下走
而入口在 $(1,1)$ 出口在 $(n,m)$
求離開迷宮最多能帶走多少寶藏
迷宮示意圖如下

很暴力的 DP

應該不難聯想到這題 CSES - Grid Paths
只要把狀態開成四維
分別代表第一個人的 xy 座標及第二個人的 xy 坐標
然後可以推出：

$$dp[i][j][k][l]=grid[i][j]+\text{max}\{\begin{array}{l}dp[i-1][j][k-1][l]\\ dp[i-1][j][k][l-1]\\ dp[i][j-1][k-1][l]\\ dp[i][j-1][k][l-1]\end{array}$$

不過加上 $grid[i][j]$ 的部份有些細節要處理
詳細轉移的部份自己看下面的程式碼

在本地測試了一下就順利通過了範測 ouob

快樂壓常時間

結果剛剛的作法傳上去之後很快就拿到 TLE 了
於是就想說順便來嘗試看看最近剛學到的壓常小技巧

#define int short

加上去後通過了更多比測資但依然還是 TLE

又仔細思考了一下題目
發現 $i+j\ne k+l$ 的狀態一定不合法
所以就把不合法的狀態 continue 掉

然後就神奇的成功壓常 AC 了 :D

程式碼

#include <bits/stdc++.h>
using namespace std;
#define int short
#define endl "\n"

const int MAXN = 1e2 + 3;
const int INF = 32000;

int mp[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    // 把邊界都設定為 -INF
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            for (int k = 0; k <= n + 1; k++) {
                for (int l = 0; l <= m + 1; l++) {
                    if (i == 0 || i == n+1 || j == 0 || j == m+1 || k == 0 || k == n+1 || l == 0 || l == m+1) {
                        dp[i][j][k][l] = -INF;
                    }
                }
            }
        }
    }
    // 初始狀態
    dp[0][0][0][0] = 0;
    dp[0][1][0][1] = 0;
    dp[1][0][1][0] = 0;
    dp[0][1][1][0] = 0;
    dp[1][1][1][1] = 0;
    // 輸入整張地圖
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
        }
    }
    // DP
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 1; k <= n; k++) {
                for (int l = 1; l <= m; l++) {
                    // 一點點剪枝
                    if (i + j != k + l) continue;
                    if (mp[i][j] == -1 || mp[k][l] == -1) {
                        dp[i][j][k][l] = -INF;
                        continue;
                    }
                    // 轉移
                    dp[i][j][k][l] = max({
                        dp[i-1][j][k-1][l],
                        dp[i-1][j][k][l-1],
                        dp[i][j-1][k-1][l],
                        dp[i][j-1][k][l-1],
                    });
                    // 拿到寶藏增加分數
                    dp[i][j][k][l] += (mp[i][j] == 1) + (mp[k][l] == 1) * (i != k || j != l);
                }
            }
        }
    }
    // 輸出答案
    cout << max(dp[n][m][n][m], (short)0) << endl;
}