P2380狗哥采矿(状态不易设计)

描述:https://www.luogu.com.cn/problem/P2380

首先分析一下，易知传送带一定是要么向上，要么向右。且一定摆满了整个矩阵。

所以我们设 f [ i ] [ j ]表示：除了从1,1到 i , j 这个矩形之外的所有地区能获得的最大矿数。

那么从上一个状态到这一个状态，有两种情况：

①从f [ i ] [ j+1 ] 的状态，在1,j+1到i,j+1铺设一条传送带。

②从f [ i+1 ] [ j ] 的状态，在i+1,1到 i+1 , j 铺设一条传送带。

所以这两种情况的最大值就是f [ i ] [ j ] 的值。

考虑到每次都要求一段区间的和，我们可以分别维护两个横向，纵向的前缀和来优化。

至于为什么答案是 f [ 0 ] [ 0 ] ，因为即使枚举到了1，1代表的意思是除了1,1这个矩阵的收益

#include <bits/stdc++.h>

using namespace std;

int n,m;

int a[][],b[][];

int hang[][],lie[][];

int dp[][];//定义除1,1到i,j矩阵，能获得的最大收益

int main()

{

    while(cin>>n>>m&&(n+m))

    {

        memset(hang,,sizeof(hang));

        memset(lie,,sizeof(lie));

        memset(dp,,sizeof(dp));

        for(int i=;i<=n;i++)    for(int j=;j<=m;j++)    cin>>a[i][j];

        for(int i=;i<=n;i++)    for(int j=;j<=m;j++)    cin>>b[i][j];

        for(int i=;i<=n;i++)    for(int j=;j<=m;j++)    hang[i][j]=hang[i][j-]+a[i][j];//预处理前缀和

        for(int j=;j<=m;j++)    for(int i=;i<=n;i++)    lie[j][i]=lie[j][i-]+b[i][j];

        for(int i=n;i>=;i--)

            for(int j=m;j>=;j--)

                dp[i][j]=max(dp[i+][j]+hang[i+][j],dp[i][j+]+lie[j+][i]);

        cout<<dp[][]<<endl;

    }

}

巴特西

P2380狗哥采矿(状态不易设计)

最新文章

热门文章