Lutece 2174 挖矿攻略

题目链接:https://acm.uestc.edu.cn/problem/wa-kuang-gong-lue/description

题目大意:给你一个矩阵,每个点上有矿物,求收集到的矿物的最大值

分析:

矿物要直线运输,这样子可以把受约束的点降到最小。

做前缀和,降低复杂度。

状态转移方程为dp[i][j]=max(dp[i-1][j]+red[i][j],dp[i][j-1]+black[i][j]);

即当前i * j块的值,为(i-1)* j块和i * (j-1)块的值,分别加上当前行和列的值的最大值。

所以使用刷表法,跑两重循环。

代码:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int red[501][501];
int black[501][501];
int dp[501][501];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n,m,linshi;
    memset(red,0,sizeof(red));
    memset(black,0,sizeof(black));
    memset(dp,0,sizeof(dp));
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cin>>linshi;
            red[i][j]=linshi+red[i][j-1];
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cin>>linshi;
            black[i][j]=linshi+black[i-1][j];
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            dp[i][j]=max(dp[i-1][j]+red[i][j],dp[i][j-1]+black[i][j]);
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注