最後更新日期 2024 / 01 / 01

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

題意

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

problem image

很暴力的 DP

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

dp[i][j][k][l]=grid[i][j]+max{dp[i1][j][k1][l]dp[i1][j][k][l1]dp[i][j1][k1][l]dp[i][j1][k][l1]

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

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

快樂壓常時間

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

#define int short

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

又仔細思考了一下題目
發現 i+jk+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;
}

推薦文章

[題解] TIOJ 2195 粉刷護欄 (TOI 2021 初選 pC)

上下有個有一根木樑 然後中間有 n 條可能會相交的木板 找出最多可以釘上幾條木板並構造最大字典序的解 細節自己去 TIOJ 看 :因為這題看起來沒人寫題解 於是我就發了這篇文章 ouob仔細觀察問題 我們可以把問題轉換成 LIS 或 LCSLCS 的話應該不難理解 因為要釘最多木板其實就是要在上下兩條陣列各選一個共同的子序列 然後把每個數字一一對應釘起來 但是 LCS 需要 On^2 的時間複雜度才能計算 所以一定會 TLE接著是 LIS 的作法 仔細觀察題目的話可以發現 如果木板有"座標"的話 其實我們在做的事情就是"對木板做 LIS" 更精確一點的說 就是我們其實可以把木板在上樑的點跟下樑的點綁成一個 pair 做 LIS 我們說木板 A 的座標小於木板 B 代表 A 的下樑座標跟上樑座標都小於 B至於座標的部分大概就是這個意思: 以附圖為例 木板 3 的座標就是 2, 1 木板 4 的座標就是 5, 3 木板 5 的座標就是 4, 4如果用最普通的 DP 方式 就算能構造解也很難求最大字典序 於是我們修改一下計算方式 把轉移式改成 "定義 dpi 為把第 i 個元當頭素能構造出的 LIS" 其實就只是倒著做 LIS 然後 Increasing 改成 Decreasing 就好了做完 DP 之後 我們要從 dp 值大的開始構造 先找一個 dp 值跟最終 LIS 一樣長而且字典序最大的元素 接著往右找小一點的直到 1 為止關於上面提到的"座標" 實際上不需要真的把座標算出來 我們只需要把第二個陣列代表下梁座標的陣列每一個元素替換成該元素在第一個陣列出現的位置 並對第二個陣列做 LIS 就可以了 ~~原因的話講起來有點麻煩 自己想吧~~第一次傳 WA 了一片 然後 debug 的時後測出這樣的測資會出錯 如果你也找不到你的程式坐在哪裡的話 不仿測試看看這筆測資33 1 21 2 3cppusing namespace std;const int MAXN = 2e5 + 10; map 會超時,所以改 unorderedmapunorderedmapint, int rpos;unorderedmapint, int pos;vectorint lensMAXN;int vMAXN;bool cmpint a, int b { return rposva rposvb;}signed main { io; int n; cin n; for int i = 1; i = n; i++ { int tmp; cin tmp; 紀錄元素座標 postmp = i; } for int i = 1; i = n; i++ { int tmp; cin tmp; 將陣列的值設定為目前元素在上面陣列的出現位置 vi = postmp; 把坐標在映射回他的值,輸出的時候會用到 rpospostmp = tmp; } LIS 的部分 作法類似: int len = 0; vectorint dp; for int i = n; i = 1; i-- { int ans = 0; 儲存目前 dp 值:以 i 為開頭能構造出多長的 LIS if dp.empty || dp.back vi { dp.pushbackvi; 紀錄目前的 dp 值 ans = dp.size; } else { auto ite = upperboundalldp, vi, greaterint; ite = vi; 紀錄目前的 dp 值 ans = ite - dp.begin + 1; } len 維護最終 LIS 長度 len = maxlen, ans; 紀錄每個長度的解 lensans.pushbacki; } 構造解 int cur = 0; for int i = len; i = 1; i-- { 依照字典序做 sort sortalllensi, cmp; for auto j : lensi { 排除在目前選到的元素左邊的元素 if j = cur continue; 排除加入後會相交的元素 用於排除文章中寫的“一個小測資”那段的 Case if vj vcur continue; cur = j; 把 index 映射回去並輸出 cout rposvj " "; break; } }}

TIOJ

題解 CSES Repetitions

你有一個由 A、C、G、T 組成的字串 目標是算出同樣的字母最多連續重複幾次把整個字串從左邊往右掃 用一個 curLen 變數維護目前的長度 遇到一個字母時 curLen 加 1 如果跟上個字母不同就把 curLen 歸零 每次掃過一個字母再用 maxLen 維護出現過最大的 curLencppusing namespace std;signed main { char chr, tmp = 'X'; int maxLen = 1, curLen = 1; while cin chr { if tmp = 'X' tmp == chr { curLen++; } else { curLen = 1; } maxLen = maxmaxLen, curLen; tmp = chr; } cout maxLen endl;}

CSES

題解 CSES Permutations

給予一個數字 n 你要使用數字 1 sim n 構造一個陣列 使得不存在任意兩個相鄰數字的差為 1把 n 個數字分成 1 sim lfloor frac{n}{2} rfloor 和 lfloor frac{n}{2}+1 rfloor sim n 兩堆 並穿插構造 ans 陣列就可以保證任兩數的差大約為 lfloorfrac{n}{2}rfloor 最後跑過整個陣列驗證是否合法即可cppusing namespace std;signed main { iosbase::syncwithstdiofalse;cin.tie0; int n; cin n; vectorint arrn; dequeint ans; int mid = n2; for int i = 1; i = n2; i ++ { int leftVal = i; int rightVal = mid + i; ans.pushbackrightVal; ans.pushbackleftVal; } if n 1 == 1 { ans.pushfrontmid + n2 +1; } for int i = 0; i n-1; i++ { if absansi+1 - ansi == 1 { cout "NO SOLUTION" endl; return 0 ; } } for int i = 0; i n; i ++ { cout ansi " "; } cout endl;}

CSES