Light OJ 1036A Refining Company

先用ma1[ i ][ j ] ,ma2[ i ][ j ]分别存從這個點往左和上運對應的礦可以運的重量

maxx[ i ][ j ]代表這個 0 ~ i -- 0 ~ j 矩形可以運的最大礦量，遞推公式mapp[ i ][ j ]=max(mapp[ i ][ j - 1 ]+ma2[ i ][ j ],mapp[ i - 1 ][ j ]+ma1[ i ][ j ])

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
using namespace std;
int ma1[505][505],ma2[505][505];
int mapp[505][505];
int main()
{
    int t,n,m,i,j,k;
    scanf("%d",&t);
    for(k=1;k<=t;k++)
    {
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&ma1[i][j]);
                ma1[i][j]+=ma1[i][j-1];
            }
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&ma2[i][j]);
                ma2[i][j]+=ma2[i-1][j];
            }
        memset(mapp,0,sizeof(mapp));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                mapp[i][j]=max(mapp[i][j-1]+ma2[i][j],mapp[i-1][j]+ma1[i][j]);
            }
        }
        printf("Case %d: %d\n",k,mapp[n][m]);

    }
    return 0;
}
//maxx[i][j]代表這個矩形可以運的最大礦量，遞推公式mapp[i][j]=max(mapp[i][j-1]+ma2[i][j],mapp[i-1][j]+ma1[i][j]);