正題

題目鏈接:https://www.luogu.com.cn/problem/P6855

---

題目大意

$n?m$的網格，每個格子有一個數，可以選擇一個位置變為$0$。要求最小化最大權值和路徑。

---

解題思路

考慮枚舉哪個位置變為$0$，一個位置變為$0$后我們將路徑分為兩種路徑，一種是經過該點的路徑，一種是不經過該點的路徑。

我們預處理出$f_{i,j}$表示$(1,1)$走到$(i,j)$的最大權和，$g_{i,j}$表示$(i,j)$走到$(n,m)$的最大權和。然后我們發現如果不走$(x,y)$這個位置，那么一會走$(i,y)?>(i,y+1)$其中$i<x$或者$(x,j)?>(x+1,j)$其中$j<y$。用$g$和$f$計算這些走法的最大權值和即可。

時間復雜度$O(nm)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2100,XJQ=998244353; ll n,m,ans,a[N][N],f[N][N],g[N][N],ar[N][N],br[N][N]; signed main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){scanf("%lld",&a[i][j]);f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];}for(ll i=n;i>=1;i--)for(ll j=m;j>=1;j--){g[i][j]=max(g[i+1][j],g[i][j+1])+a[i][j];ar[i][j]=f[i][j]+g[i+1][j];br[i][j]=f[i][j]+g[i][j+1];}ans=1e18;for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++){ll z=max(f[i][j]+g[i][j]-2*a[i][j],max(ar[i][j-1],br[i-1][j]));ans=min(ans,z);if(j!=1)ar[i][j]=max(ar[i][j],ar[i][j-1]);if(i!=1)br[i][j]=max(br[i][j],br[i-1][j]);}printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的P6855-「EZEC-4.5」走方格【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。