题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=25913
思路：易证存在一条从左上角到右下角的折线，沿着格子边缘的...其中处于折线下方的全部运送到左边去，其他运送到上边去...那么这个折线就相当于从上面走到下面得分最大...直接dp就可以。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define FILL(a,b) memset(a,b,sizeof(a)) 7 8 int n,m,Ura[555][555],Rad[555][555]; 9 int dp[555][555]; 10 11 int main() 12 { 13 int _case,t=1; 14 scanf("%d",&_case); 15 while(_case--){ 16 scanf("%d%d",&n,&m); 17 for(int i=1;i<=n;i++) 18 for(int j=1;j<=m;j++)scanf("%d",&Ura[i][j]); 19 for(int i=1;i<=n;i++) 20 for(int j=1;j<=m;j++)scanf("%d",&Rad[i][j]); 21 for(int i=1;i<=n;i++) 22 for(int j=1;j<=m;j++)Ura[i][j]+=Ura[i][j-1]; 23 for(int i=1;i<=n;i++) 24 for(int j=1;j<=m;j++)Rad[i][j]+=Rad[i-1][j]; 25 FILL(dp,0); 26 for(int i=1;i<=n;i++) 27 for(int j=1;j<=m;j++)dp[i][j]=max(dp[i][j-1]+Rad[i][j],dp[i-1][j]+Ura[i][j]); 28 printf("Case %d: %d ",t++,dp[n][m]); 29 } 30 return 0; 31 }