描述:https://www.luogu.com.cn/problem/P2380
首先分析一下，易知传送带一定是要么向上，要么向右。且一定摆满了整个矩阵。
所以我们设 f [ i ] [ j ]表示：除了从1,1到 i , j 这个矩形之外的所有地区能获得的最大矿数。
那么从上一个状态到这一个状态，有两种情况：
①从f [ i ] [ j+1 ] 的状态，在1,j+1到i,j+1铺设一条传送带。
②从f [ i+1 ] [ j ] 的状态，在i+1,1到 i+1 , j 铺设一条传送带。
所以这两种情况的最大值就是f [ i ] [ j ] 的值。
考虑到每次都要求一段区间的和，我们可以分别维护两个横向，纵向的前缀和来优化。
至于为什么答案是 f [ 0 ] [ 0 ] ，因为即使枚举到了1，1代表的意思是除了1,1这个矩阵的收益
#include <bits/stdc++.h> using namespace std; int n,m; int a[509][509],b[509][509]; int hang[509][509],lie[509][509]; int dp[509][509];//定义除1,1到i,j矩阵，能获得的最大收益 int main() { while(cin>>n>>m&&(n+m)) { memset(hang,0,sizeof(hang)); memset(lie,0,sizeof(lie)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>b[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) hang[i][j]=hang[i][j-1]+a[i][j];//预处理前缀和 for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) lie[j][i]=lie[j][i-1]+b[i][j]; for(int i=n;i>=0;i--) for(int j=m;j>=0;j--) dp[i][j]=max(dp[i+1][j]+hang[i+1][j],dp[i][j+1]+lie[j+1][i]); cout<<dp[0][0]<<endl; } }