题目大意：
一个n*m的矩阵，每个点上有两种物质
两种物质分别只能向左或向上运输直到左边界或上边界
一个点只能开采一种物质
并且若该物质只能向左运，则其正左边所有物质都只能选向左的物质；若该物质只能向上运，则其正上方所有物质都只能选向上的物质
思路：
n m <=500
dp
先打一个横着和竖着的前缀和，然后对于每个点可以从它左边的点或上方的点转移过来
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<queue> 8 #include<vector> 9 #include<map> 10 #include<stack> 11 #define inf 2147483611 12 #define ll long long 13 #define MAXN 510 14 using namespace std; 15 inline int read() 16 { 17 int x=0,f=1; 18 char ch;ch=getchar(); 19 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 20 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 21 return x*f; 22 } 23 int n,m,x,sx[MAXN][MAXN],sy[MAXN][MAXN],dp[MAXN][MAXN]; 24 int main() 25 { 26 while(scanf("%d%d",&n,&m)&&n&&m) 27 { 28 for(int i=1;i<=n;i++) 29 for(int j=1;j<=m;j++) x=read(),sx[i][j]=sx[i][j-1]+x; 30 for(int i=1;i<=n;i++) 31 for(int j=1;j<=m;j++) x=read(),sy[i][j]=sy[i-1][j]+x; 32 for(int i=1;i<=n;i++) 33 for(int j=1;j<=m;j++) 34 { 35 dp[i][j]=max(dp[i-1][j]+sx[i][j],dp[i][j-1]+sy[i][j]); 36 } 37 printf("%d ",dp[n][m]); 38 } 39 }