【每日一題】【前綴和優化】【前/后綴最值】牛客練習賽139 B/C題大衛的密碼 (Hard Version) C++

牛客練習賽139 B題大衛的密碼 (Easy Version)
牛客練習賽139 C題大衛的密碼 (Hard Version)

大衛的密碼

題目背景

牛客練習賽139

題目描述

給定一個 $n\times m$ 的網格圖，我們使用 $(i, j)$ 表示網格中從上往下數第 $i$ 行和從左往右數第 $j$ 列的單元格。左上角為 $(1, 1)$ ，右下角為 $(n, m)$ ，每個格子包含一個整數價值，使用 $a_{i,j}$ 表示。
一個光標在上面移動，從 $(s, 1)$ 出發，每次可以向右或者向下移動，每個格子至多經過一次。當光標移動到 $(n,i)(1\le i \le m)$ 格子，也就是最后一行的某個格子時，繼續向下移動則會到達 $(1, i)$ 格子。大衛需要移動光標到達 $(t, m)$ ，求最終大衛能獲取的最大價值和。
注意本題的時間限制。本題數據量較大，我們建議您選取較快的讀入方式。

輸入格式

第一行輸入四個整數 $m,s,t(1\le n ,m \le 2\times10^3;1\le s,t \le n)$
注:簡單版本的范圍是： $1\le n ,m \le 500$
此后 $n$ 行，第 $i$ 行輸入 $m$ 個整數 $a_{i,1},a_{i,2},...,a_{i,m}(-5\times 10^4\le a_{i,j} \le 5\times 10^4)$ ,表示一個格子的價值

輸出格式

在一行上輸出一個整數，表示大衛能獲取的最大價值和。

樣例 #1

樣例輸入 #1

樣例輸出 #1

說明

小紅失去向上走的能力，消除 $(1, 3)$ 處障礙，從起點到終點的最小步數為 $6$ 。

樣例 #2

樣例輸入 #2

5 5 1 5
6 10 4 10 6
-6 6 10 3 -1
-10 9 -6 -10 10
-3 8 4 5 6
-5 -8 2 4 8

樣例輸出 #2

做題要點

每次可以向右或者向下移動（說明不能往回走）
每個格子至多經過一次
時間給的是2s
到某一列的最后一行在往下就到該列的第一行

做題思路

先考慮簡單版本

首先因為 $1\le n ,m \le 500$ ，所以哪怕是 $O(n^3) / O(m \times n^2) / O(n \times m^2)$ 都可以考慮

逆向思考

這里設 $dp_{i,j}$ 表示從起點走到 $(i, j)$ 點的大衛能獲取的最大價值和。
從某一點 $(i, j)$ 考慮，那么答案一定是
$dp_{i,j} = \begin{cases} \max{(dp_{i,j-1},dp_{i-1,j})} + a_{i,j} , (i\neq s , j \neq 1) \\ dp_{i,j} = a_{i,j} ,(i = s , j = 1)\end{cases}$
加上記憶化搜索后dfs代碼：

int dfs(int i,int j,int k){if(vis[i][j])return dp[i][j];vis[i][j] = true;if(i == s && j == 1)return dp[i][j] = a[i][j];int k1=-inf,k2=-inf;if(j != 1)k1=dfs(i,j_f(j),0);if(k < n-1)k2 = max(k2,dfs(i_f(i),j,k+1));return dp[i][j]=max(k1,k2) + a[i][j];
}

但是注意到某一列的最后一行在往下就到該列的第一行，所以就會出現一個環，導致遞推式無法完全計算。
注意： $dp_{i,j} = \max{(dp_{i,j-1},dp_{i-1,j})} + a_{i,j}$
那么 $dp_{i,j}$ 的答案依賴于 $dp_{i,j-1}$ 和 $dp_{i-1,j}$ ，如果只關注后面的那個依賴關系
那么就會有
$dp_{2,j}$ 依賴于 $dp_{1,j}$ ；
$dp_{1,j}$ 依賴于 $dp_{m,j}$ ；
$dp_{m,j}$ 依賴于 $dp_{m-1,j}$
$dp_{m-1,j}$ 依賴于 $dp_{m-2,j}$
…
$dp_{3,j}$ 依賴于 $dp_{2,j}$
最后就會發現 $dp_{i,j}$ 依賴于自己 $dp_{i,j}$ ( $j\neq 1$ )。如果依賴符號用有向箭頭連接成一個有向圖，就會發現是一個環。所以此寫法欠缺考慮。

注：如果不考慮記憶化搜索優化，會TLE

int dfs(int i,int j,int k){if(i == s && j == 1)return a[i][j];int k1=-inf,k2=-inf;if(j != 1)k1=dfs(i,j_f(j),0);if(k < n-1)k2 = max(k2,dfs(i_f(i),j,k+1));return max(k1,k2) + a[i][j];
}

正向思考

但剛剛的逆向思考中，會發現除了第一列的 $dp_{i,1}$ 都得到了答案，其他都是未知的或錯解。
其根本原因是 $(s, 1)$ 的點是起點， $dp_{s,1}$ 不依賴于（其他）未知的量，更不依賴于本身。
至此第一列的答案都是可以由 $dp_{s,1}$ 推出的定值
那假設從第一行第一列往第一行第二列走。并且設其 $dp_{1,2} = dp_{1,1} + a_{1,2}$ 。這樣一來就達到了破環的效果，再用第一列的方法，一直向下推，可以推出其中一組 $dp_{i,2}$ 解。
同理如果從第二行第一列從第二行第二列走。并且設其 $dp_{2,2} = dp_{2,1} + a_{2,2}$ 。這樣一來也就達到了破環的效果，再用第一列的方法，一直向下推，可以推出又一組 $dp_{i,2}$ 解。
…
同理如果從第 $n$ 行第一列從第 $n$ 行第二列走。并且設其 $dp_{n,2} = dp_{n,1} + a_{n,2}$ 。這樣一來也就達到了破環的效果，再用第一列的方法，一直向下推，可以推出又一組 $dp_{i,2}$ 解。

然后在 $dp_{i,2}$ 解組( $n$ 組解) 中選擇最大的值當作 $dp_{i,2}$ 的解即可
然后第二列的答案都是定值了
以此類推直到最后一列
由此我們得到了第二個遞推式:
設 $fdp_{k,i,j}$ 表示從第 $k$ 行第 $j ? 1$ 列往第 $k$ 行第 $j$ 列走后推出的一組解,并且設其 $fdp_{k,k,j} = dp_{k,j-1} + a_{k,j}$
并且推出一組解的遞推式為:
$fdp_{k,i,j} = fdp_{k,i-1,j} + a_{i,j} , (i \neq k)$
得到所以 $m$ 組解后，真正的答案選取最大的即可：
$dp_{i,j} = \displaystyle\max_{k=1}^n{(fdp_{k,i,j})}$
由第一列為定值推出第二列的值，可以將第二列看為定值推第三列，以此類推。
換句話說由第一列為定值推出第二列的值其實是枚舉第二列的“起點”

#define RIP(i,j,k) for(int (i) = (j) ; (i) < (k) ; ++ i)
inline int f_i(int x){return x + 1 == n + 1 ? 1 : x + 1;}//往下
inline int i_f(int x){return x - 1 == 0 ? n : x - 1; }//往上
int ans[N][N];
bool vis[N][N]
RIP(j,1,m+1){for(int i = s ; !vis[i][j] ; i = f_i(i)){//枚舉起點/轉移行int ansi[N];//fdpvis[i][j] = true;ansi[i] = a[i][j] + ans[i][j-1];for(int k = f_i(i); k != i ; k = f_i(k)){ansi[k] = a[k][j] + ansi[i_f(k)];//fdp[i]  = fdp[i-1] + a[i][j]}//得到一組答案RIP(k,1,n+1)ans[k][j] = max(ans[k][j] , ansi[k]);//更新這一組答案if(j==1)break;//第一列的起點就一個}}

注意第一列的起點就一個！
總時間復雜度為 $O(m\times n^2)$ ，在簡單版本可以通過，但困難版本數據范圍放大后就會TLE

如果要考慮通過困難版本就需要優化
將遞推式 $dp_{i,j} = \displaystyle\max_{k=1}^n{(fdp_{k,i,j})}$ 展開就會有
$dp_{i,j} = \displaystyle\max_{k=1}^n dp_{k,j-1} + \displaystyle\sum_{o=k}^i a_{o,j}$
其中 $\displaystyle\sum_{o=k}^i a_{o,j}$ 表示從第 $k$ 行第 $j$ 列一直向下走直到第 $i$ 行第 $j$ 列的路徑上的權值和。
那么重點是每次算這個路徑權值和的時候是最里面的一層循環，并且還要求最大值。

for(int k = f_i(i); k != i ; k = f_i(k)){ansi[k] = a[k][j] + ansi[i_f(k)];//fdp[i]  = fdp[i-1] + a[i][j]}//得到一組答案RIP(k,1,n+1)ans[k][j] = max(ans[k][j] , ansi[k]);//更新這一組答案

這時候如果路徑權值和能立馬得到那么循環常數就可能會減少。如果把這一列數字單獨拿出來當作一個數組 $b_i$ ，其實就是要求 $\displaystyle\sum_{i=l}^r b_i$
相當于多次要求區間和，我們可以考慮前綴和預處理優化。
設 $pre_n = \displaystyle\sum_{i=1}^n b_n = \displaystyle\sum_{i=1}^n a_{n,j} (j為固定值)$
因為是一列一列考慮的所以j為固定值。相當于原本是:
$pre_{n,j} =\displaystyle\sum_{i=1}^n a_{n,j}$ “滾動化”
所以以下式子默認 $pre_n = pre_{n,j}$

接下來改寫遞推式，繼續展開
$dp_{i,j} = \max dp_{k,j-1} + \begin{cases}pre_i - pre_{k-1} , i \ge k \\ pre_n - pre_{k-1} + pre_i , i \lt k \end{cases}$

將預處理后的共同已知量提到 $\max$ 外面得
$dp_{i,j} = pre_i + \max dp_{k,j-1} + \begin{cases} - pre_{k-1} , i \ge k \\ pre_n - pre_{k-1} , i \lt k \end{cases}$

然而如果每個 $i$ 都枚舉一遍 $k$ 時間復雜度依舊是 $O(m\times n^2)$ ，這時候就需要預處理 $k$ 和 $i$ 的關系
假設 $G_i$ 表示 $\max dp_{k,j-1} - pre_{k-1}, i \ge k$
假設 $L_i$ 表示 $\max dp_{k,j-1} + pre_n - pre_{k-1} , i \lt k$
那么原遞推式就能寫成
$dp_{i,j} = pre_i + \max (G_i,L_i)$
遞推式就是只用枚舉 $i$
那么問題就在于如何用線性時間復雜度預處理解出 $G_i$ 和 $L_i$
從式子上發現 $G_i$ 只與 $k$ 有關。也就是說
$G_{1} = dp_{1,j-1} - pre_{0}$ ，(相當于 $k$ 只能選 $\set{1}$ )
$G_{2} = \max(dp_{1,j-1} - pre_{0} , dp_{2,j-1} - pre_{1}) = \max(G_1,dp_{2,j-1} - pre_{1})$ ，(相當于 $k$ 只能選 $\set{1,2}$ )
同理 $G_3 = \max{(G_2 , dp_{3,j-1} - pre_{2})}$
以此類推 $G_i = \max{(G_{i-1} , dp_{i,j-1} - pre_{i-1})}$

$L_i$ 只與 $k$ 有關，
$L_n = -inf (無)$ ， (相當于 $k$ 沒得選)
$L_{n-1} = dp_{n,j-1} + pre_{n} - pre_{n-1}$ ，(相當于 $k$ 只能選 $\set{n}$ )
同理 $L_{n-2} = \max{(L_{n-1},dp_{n-1,j-1} + pre_{n} - pre_{n-2})}$
以此類推 $L_i = \max{(L_{i+1} , dp_{i+1,j-1} + pre_n - pre_{i})}$

RIP(j,1,m+1){int pre[N],L[N],G[N];RIP(i,0,n+1){pre[i] = 0;L[i] = G[i] = -inf;}RIP(i,1,n+1)pre[i] = pre[i-1] + a[i][j];RIP(i,1,n+1)G[i] = max(G[i-1],ans[i][j-1]-pre[i-1]);L[n] = -inf;L[n-1]=ans[n][j-1]+pre[n]-pre[n-1];rRIP(i,n-2,1)L[i]= max(L[i+1],ans[i+1][j-1] + pre[n] - pre[i]);RIP(i,1,n+1)ans[i][j] = pre[i] + max(L[i],G[i]);}

最后用上起點，和之前的思路一樣。第一列只有一個起點，也就是說我們要保證
$dp_{s,0} = 0 且 dp_{s,0} >> dp_{i,0} (i\neq s)$ （保證不能選到（有）從非起點行第0列轉移到第一列的任意行的情況）
所以設置 $dp_{i,0} = -inf (i\neq s)$

RIP(i,1,n+1)ans[i][0]=-inf;ans[s][0]=0;

時間復雜度為 $O(m\times n)$

代碼

#include <bits/stdc++.h>
#define int long long
#define RIP(i,j,k) for(int (i) = (j) ; (i) < (k) ; ++ i)
#define rRIP(i,j,k) for(int (i) = (j) ; (i) >= (k) ; -- i)
#define all(x) x.begin(),x.end()
#define endy {cout << "YES" << '\n'; return; }
#define endn {cout << "NO" << '\n'; return; }
#define endx(x) {cout << (x) << '\n'; return; }
#define conti(x) {cout << (x) << '\n';continue;}
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
using namespace std;
using i128 = __int128;
using pii = pair<int,int>;
using tiii = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vii = vector<pii>;
using mii = map<int,int>;
const int N = 2e3+10;
const int mod = 1e9 + 7;
const int MID = 2e4+10;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n = 1 , m  = 100 , s , t;int a[N][N];
int ans[N][N];
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * w;
}
inline int f_j(int x){return x + 1 == m + 1 ? 1 : x + 1; }
inline int j_f(int x){return x - 1 == 0 ? m : x - 1; }
inline int f_i(int x){return x + 1 == n + 1 ? 1 : x + 1;}
inline int i_f(int x){return x - 1 == 0 ? n : x - 1; }
void solve(){n = read() , m = read() , s = read() , t = read();RIP(i,1,n+1)RIP(j,1,m+1){a[i][j] = read();ans[i][j] = -inf;}RIP(i,1,n+1)ans[i][0]=-inf;ans[s][0]=0;RIP(j,1,m+1){int pre[N],L[N],G[N];RIP(i,0,n+1){pre[i] = 0;L[i] = G[i] = -inf;}RIP(i,1,n+1)pre[i] = pre[i-1] + a[i][j];RIP(i,1,n+1)G[i] = max(G[i-1],ans[i][j-1]-pre[i-1]);L[n] = -inf;L[n-1]=ans[n][j-1]+pre[n]-pre[n-1];rRIP(i,n-2,1)L[i]= max(L[i+1],ans[i+1][j-1] + pre[n] - pre[i]);RIP(i,1,n+1)ans[i][j] = pre[i] + max(L[i],G[i]);}cout << ans[t][m];
}
signed main(){//IOS//int T;cin >> T;while(T--)solve();
}

簡單版本

#include <bits/stdc++.h>
#define int long long
#define RIP(i,j,k) for(int (i) = (j) ; (i) < (k) ; ++ i)
#define rRIP(i,j,k) for(int (i) = (j) ; (i) >= (k) ; -- i)
#define all(x) x.begin(),x.end()
#define endy {cout << "YES" << '\n'; return; }
#define endn {cout << "NO" << '\n'; return; }
#define endx(x) {cout << (x) << '\n'; return; }
#define conti(x) {cout << (x) << '\n';continue;}
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
using namespace std;
using i128 = __int128;
using pii = pair<int,int>;
using tiii = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vii = vector<pii>;
using mii = map<int,int>;
const int N = 2e3+10;
const int mod = 1e9 + 7;
const int MID = 2e4+10;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n = 1 , m  = 100 , s , t;int a[N][N];
int ans[N][N];
bool vis[N][N];
int pre[N][N];
int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * w;
}
inline int f_j(int x){return x + 1 == m + 1 ? 1 : x + 1; }
inline int j_f(int x){return x - 1 == 0 ? m : x - 1; }
inline int f_i(int x){return x + 1 == n + 1 ? 1 : x + 1;}
inline int i_f(int x){return x - 1 == 0 ? n : x - 1; }
void solve(){n = read() , m = read() , s = read() , t = read();RIP(i,1,n+1)RIP(j,1,m+1){a[i][j] = read();ans[i][j] = -inf;}RIP(j,1,m+1)RIP(i,1,n+1)pre[i][j] = pre[i-1][j] + a[i-1][j];RIP(j,1,m+1){for(int i = s ; !vis[i][j] ; i = f_i(i)){int ansi[N];vis[i][j] = true;ansi[i] = a[i][j] + ans[i][j-1];for(int k = f_i(i); k != i ; k = f_i(k)){ansi[k] = a[k][j] + ansi[i_f(k)];}RIP(k,1,n+1)ans[k][j] = max(ans[k][j] , ansi[k]);if(j==1)break;}}cout << ans[t][m];
}
signed main(){//IOS//int T;cin >> T;while(T--)solve();
}