51Nod1084矩阵取数问题 V2

题意：

一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。

solution:

把题目转化成两个人从左上角出发，走到右下角的奖励之和

设dp[i][j][p][q]为第一个人在(i,j)点，第二个人在(p,q)点的最大奖励之和

四重循环复杂度爆炸

我们发现i+j=p+q;

所以转化为dp[k][i][j]为走了k步，第一个人在i行，第二个人在j行，列可以用k-i，k-j表示

并可以用滚动数组优化

注意i=j时只需要加一个值

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 int n,m,f[][],s[][];

 int main(){

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

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

         for(int j=;j<=m;++j) scanf("%d",s[i]+j);

     for(int k=;k<=m+n;++k) for(int i=n;i;--i) for(int j=n;j;--j)

         f[i][j]=max(max(f[i][j],f[i-][j-]),max(f[i-][j],f[i][j-]))+s[i][k-i]+(i!=j?s[j][k-j]:);

     printf("%d\n",f[n][n]);

 }

巴特西

dp，滚动数组优化

51Nod1084矩阵取数问题 V2

题意：

solution:

矩阵取数问题 V2

最新文章

热门文章