双倍经验。

思路

这是一道简单的二维动态规划问题，在每一步向北或向西走时，比较到达该点时，向北走和向西走路上该种矿物的数量总和，并取大的一个。

为了计算更快，可以通过建立 $a$，$b$ 两个前缀和数组来表示该路径上两种矿物的多少。

状态转移

根据思路，不难得出，状态转移方程为：

$$ dp[i][j]=\max(a[i][j]+dp[i-1][j],b[i][j]+dp[i][j-1]) $$

其中 dp[i][j] 代表从 $(1,1)$ 到 $(i,j)$ 的矩阵中最大的采矿量，a[i][j] 和 b[i][j] 分别为 A 矿和 B 矿的二维前缀和，表示采到 $(i,j)$ 所必须经过（即途中必须采集）的矿物数量总和。

结束标志为 $(n,m)$，则答案为 dp[n][m]，输出即可。

代码实现

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
int n,m;
int A[505][505],B[505][505];//前缀和数组
int dp[505][505];
inline void solve()//dp
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=max(A[i][j]+dp[i-1][j],B[i][j]+dp[i][j-1]);//状态转移
        }
    }
    cout<<dp[n][m];
}
inline void pre()
{
    while(cin>>n>>m and n and m)//n=0 且 m=0 时退出不执行
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>A[i][j];
                A[i][j]+=A[i][j-1];//前缀和
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>B[i][j];
                B[i][j]+=B[i-1][j];//前缀和
            }
        }
        solve();
        puts("");
    }
} 
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    pre();
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

时间复杂度：$O(nm)$。