傳送門
走兩次
dp[x1][y1][x2][y2]表示兩條路分別到兩個點的坐標后的最大值
為了防止走重，dp[x1][y1][x1][y1]賦值為無窮小
時間復雜度O（n^4）

代碼

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=60; int a[N][N],dp[N][N][N][N]; int m,n; int max4(int a,int b,int c,int d){return max(a,max(b,max(c,d))); } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);}for(int x1=1;x1<=n;x1++){for(int y1=1;y1<=m;y1++){for(int x2=1;x2<=n;x2++){for(int y2=1;y2<=m;y2++){if(x1==x2&&y1==y2&&(x1!=n||y1!=m)) dp[x1][y1][x2][y2]=-2e9;else{dp[x1][y1][x2][y2]=max4(dp[x1-1][y1][x2-1][y2]+a[x1][y1]+a[x2][y2],dp[x1-1][y1][x2][y2-1]+a[x1][y1]+a[x2][y2],dp[x1][y1-1][x2-1][y2]+a[x1][y1]+a[x2][y2],dp[x1][y1-1][x2][y2-1]+a[x1][y1]+a[x2][y2]);}}}}}printf("%d",dp[n][m][n][m]); } /* 3 3 0 3 9 2 8 5 5 7 0 */

優化

用k表示走的步數
dp[k][y1][y2]表示兩條路徑走到的點縱坐標分別為y1y2
那么橫坐標分別為k-y1+2,k-y2+2
注意橫坐標也必須在1到m的范圍內

代碼

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=60; int a[N][N],dp[2*N][N][N]; int m,n; int max4(int a,int b,int c,int d){return max(a,max(b,max(c,d))); } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);}for(int k=1;k<=n+m-2;k++){for(int y1=1;y1<=m;y1++){if(k-y1+2<1||k-y1+2>n) continue;for(int y2=1;y2<=m;y2++){if(k-y2+2<1||k-y2+2>n){continue;}if(y1==y2&&(y1!=m||k-y1+2!=n)) dp[k][y1][y2]=-2e9;else dp[k][y1][y2]=max4(dp[k-1][y1][y2],dp[k-1][y1-1][y2-1],dp[k-1][y1-1][y2],dp[k-1][y1][y2-1])+a[k-y1+2][y1]+a[k-y2+2][y2];}}}printf("%d",dp[n+m-2][m][m]); } /* 3 3 0 9 9 6 1 8 2 3 0 */

心得

本題之前做過，但仍然不耽誤忘
主要是沒有想到賦值成無窮小的方法以去除決策
學廢了

總結

以上是生活随笔為你收集整理的不止代码 洛谷P1006 传纸条（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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