Light OJ 1036 - A Refining Company

题目大意：

一个m*n的矩阵，里面有两种矿物质铀和镭，现在要把铀和镭运送到指定位置。北边是炼镭厂，西边是了炼铀厂。

现在要建立传送带，传送带有两种，一种是从东到西，另一种是从南到北，传送带不能交叉，并且运送中途不能中断。现在你要计算出最多能采集多少矿。

输入数据：第一个m*n的矩阵代表铀的矿物质分布， 第二个矩阵代表镭的矿物质分布。

题目分析：

记忆化搜索写起来比较方便点，把数据进行一下简单的预处理就行了。

 

 

 

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

const int INF = 1e9+;

const int MAXN = ;

int dp[MAXN][MAXN];

int Ur[MAXN][MAXN], Ra[MAXN][MAXN];

int DFS(int m,int n)

{

    if(dp[m][n] != -)

        return dp[m][n];

    if(m ==  || n == )

        return dp[m][n] = ;

    dp[m][n] = max(dp[m][n], Ra[m][n] + DFS(m,n-) );///选取镭

    dp[m][n] = max(dp[m][n], Ur[m][n] + DFS(m-,n) );///选取铀

    return dp[m][n];

}

int main()

{

    int T, n, m, a, cas = ;

    scanf("%d", &T);

    while(T --)

    {

        scanf("%d %d", &m, &n);

        memset(Ur, , sizeof(Ur));

        memset(Ra, , sizeof(Ra));

        memset(dp, -, sizeof(dp));

        for(int i=; i<=m; i++)

        for(int j=; j<=n; j++)

        {

            scanf("%d", &a);

            Ur[i][j] = Ur[i][j-] + a;

        }

        for(int i=; i<=m; i++)

        for(int j=; j<=n; j++)

        {

            scanf("%d", &a);

            Ra[i][j] = Ra[i-][j] + a;

        }

        printf("Case %d: %d\n", cas ++, DFS(m,n));

    }

    return ;

}