題目不難，卻想了好長時間，目測自己DP還是很水。。。囧
思路：舍f[i][j]為前i行j列的最大礦總量不難推出狀態轉移方程為f[i][j]=max(f[i-1][j]+line[i][j],f[i][j-1]+row[j][i])
其中line[i][j]為第i行前j個A礦的和（a[i][1]+a[i][2]+...+a[i][j]）,row[i][j]為第i列前j個B礦的和（b[i][1]+b[i][2]+...+b[i][j]）
result:
代碼如下：
?
#include <cstdio>
inline int max(int x,int y)
{return x>y?x:y;
}
int a[510][510],b[510][510],f[510][510],n,m,line[510][510],row[510][510];
int main()
{int i,j;while (scanf("%d%d",&n,&m) && (n || m)){for (i=1; i<=n; ++i)for (j=1; j<=m; ++j)scanf("%d",&a[i][j]);for (i=1; i<=n; ++i)for (j=1; j<=m; ++j)scanf("%d",&b[i][j]);for (i=1; i<=n; ++i)for (j=1; j<=m; ++j)line[i][j]=line[i][j-1]+a[i][j];for (i=1; i<=m; ++i)for (j=1; j<=n; ++j)row[i][j]=row[i][j-1]+b[j][i];for (i=1; i<=n; ++i)for (j=1; j<=m; ++j)f[i][j]=max(f[i-1][j]+line[i][j],f[i][j-1]+row[j][i]);printf("%d\n",f[n][m]);}return 0;
}
?
?
