題目傳送門
前言
每次準備摸魚時都在這道題的界面。
今天有空做做,順便寫一波題解,畢竟估值蹭蹭往下跳。
雙倍經驗:P1004 [NOIP 2000 提高組] 方格取數,P1006 [NOIP 2008 提高組] 傳紙條。
題意簡述
現有一個 m m m 行 n n n 列的矩陣,每個位置上都有一個 [ 0 , 100 ] [0, 100] [0,100] 的整數。
你需要在這個矩陣上走兩遍,第一遍從左上走到右下,這時你只能向下、向右走。第二遍從右下走到左上,這是你只能向上、向左走。要求兩條路徑不能有重合(矩陣的左上角與右下角除外)。
請你求出這兩條路徑所經過的點的總和的最大值。
解題思路
如果你做過 P1004 [NOIP 2000 提高組] 方格取數,那么改一下輸入就能過。
但是為什么 dp 式子不用改?且聽我慢慢道來。
眾所周知,這道題從右下走到左上與從左上做到右下是等價的。所以,我們巧妙的將這道題轉化為了:從左上走到右下,被走過的點不能再走,再從左上走到右下所經過的點的總和的最大值。
于是我們定義 d p i , j , k , l dp_{i, j, k, l} dpi,j,k,l? 為第一遍走到了 ( i , j ) (i,j) (i,j),第二遍走到了 ( k , l ) (k,l) (k,l) 時的最大值。那么狀態轉移方程就是
d p i , j , k , l = { max ? { d p i ? 1 , j , k ? 1 , l , d p i ? 1 , j , k , l ? 1 , d p i , j ? 1 , k ? 1 , l , d p i , j ? 1 , k , l ? 1 } + a i , j + a k , l , if? i ≠ k ∧ j ≠ l ∨ ( i = 1 ∧ j = 1 ∨ i = m ∧ j = n ) ? 1 , if? i = k ∧ j = l ∧ ? ( i = 1 ∧ j = 1 ∨ i = m ∧ j = n ) \begin{equation*} dp_{i, j, k, l} = \begin{cases} \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}\} + a_{i,j} + a_{k,l}, & \text{if } i \neq k \land j \neq l \lor (i = 1 \land j = 1 \lor i = m \land j = n) \\ -1, & \text{if } i = k \land j = l \land \neg(i = 1 \land j = 1 \lor i = m \land j = n) \end{cases} \end{equation*} dpi,j,k,l?={max{dpi?1,j,k?1,l?,dpi?1,j,k,l?1?,dpi,j?1,k?1,l?,dpi,j?1,k,l?1?}+ai,j?+ak,l?,?1,?if?i=k∧j=l∨(i=1∧j=1∨i=m∧j=n)if?i=k∧j=l∧?(i=1∧j=1∨i=m∧j=n)??
是不是看起來很復雜?實際上也就只是 LaTeX \LaTeX LATE?X 輸起來復雜。如果懶得看以上形式,直接看代碼就行。
CODE:
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[60][60];
int dp[60][60][60][60];
signed main() {ios::sync_with_stdio(false);ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);int m, n;cin >> m >> n;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {cin >> a[i][j];}}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= m; k++) {for (int l = 1; l <= n; l++) {dp[i][j][k][l] = max(dp[i - 1][j][k - 1][l], dp[i - 1][j][k][l - 1]);dp[i][j][k][l] = max(dp[i][j - 1][k - 1][l], max(dp[i][j][k][l], dp[i][j - 1][k][l - 1]));dp[i][j][k][l] += a[i][j] + a[k][l];if (i == k && j == l && !(i == 1 && j == 1 || i == m && j == n)) {dp[i][j][k][l] = -114514;}}}}}cout << dp[m][n][m][n];return 0;
}