luogu 题解 P2380 【狗哥采矿】

拿到dp题我们就要想如何推方程

“最北边有bloggium的收集站，最西边有 yeyenum 的收集站。现在要你在这些格子上面安装向北或者向西的传送带(每个格子只能装一种)。”

这说明了什么，对于某一个点，是不是只能通过2种方式来获取这个点的值，一个是铺北的传送带，一个是铺西的传送带。然而，如果在这个点铺了传送带的话，说明整一行都会被铺，但由于后来的可以铺不同的传送带来获取该点的值，说明如果在这个点铺的话只会影响这个点的西边的点或北边的点。

综上所述，我们对于仍以一个点，需要考虑以什么形式来铺，然而会影响前面，所以我们要考虑用前缀和来维护

则可以十分轻松的推出方程
f[i][j]=max(f[i][j-1]+a[i][j],f[i-1][j]+b[i][j]);
其中a数组时i行j列向北的前缀和数组，b数组就是向西的

AC代码

 #include <cstdio>

 #include <algorithm>

 #define MAXN 510

 using namespace std;

 int f[MAXN][MAXN];

 int a[MAXN][MAXN];

 int b[MAXN][MAXN];

 int n,m;

 int temp=-;

 int main() {

 　　while(scanf("%d%d",&n,&m)) {

 　　if(n==||m==) break;

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

 　　for(int j=;j<=m;j++) {

 　　　　scanf("%d",&temp);

 　　　　b[i][j]=b[i][j-]+temp;

 　　}

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

 　　for(int j=;j<=m;j++) {

 　　　　scanf("%d",&temp);

30　　　　 a[i][j]=a[i-][j]+temp;

 　　}

 　　temp=-;

 　　for(int i=;i<=n;i++) {

 　　　　for(int j=;j<=m;j++) {

 　　　　　　f[i][j]=max(f[i][j-]+a[i][j],f[i-][j]+b[i][j]);

 　　　　　　temp=max(f[i][j],temp);

 　　　　}

 　　}

 　　printf("%d\n",temp);

 　　}

 　　return ;

 }

巴特西

luogu 题解 P2380 【狗哥采矿】

拿到dp题我们就要想如何推方程

最新文章

热门文章