矩阵取数问题 V2 51Nod - 1084

本文主要是介绍矩阵取数问题 V2 51Nod - 1084，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.51nod.com/Challenge/Problem.html#!#problemId=1084

考虑dp的话 最笨的方法就是dp[i][j][x][y]代表第一条路走到(i,j) 第二条路走到(x,y)时的最大值 dp[n][m][n][m]即为所求

转移方程：dp[i][j][x][y]=max(dp[i-1][j][x-1][y],dp[i-1][j][x][y-1],dp[i][j-1][x-1][y],dp[i][j-1][x][y-1])+e[i][j]+e[x][y]*(!(i==x&&j==y))

但是只有当(i+j)==(x+y)时 方程的转移才是有效的 所以外循环改为步数 内两层循环为两条路的横坐标 纵坐标直接通过步数算出来

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e2+10;
const int maxm=2e2+10;
const int maxs=4e2+10;int dp[maxs][maxn][maxm];
int e[maxn][maxm];
int n,m;int main()
{int i,j,k,ii,jj;scanf("%d%d",&m,&n);for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%d",&e[i][j]);}}for(k=1;k<=n+m-1;k++){for(i=1;i<=k&&i<=n;i++){for(j=1;j<=k&&j<=n;j++){ii=k+1-i,jj=k+1-j;dp[k][i][j]=max(max(dp[k-1][i][j],dp[k-1][i][j-1]),max(dp[k-1][i-1][j],dp[k-1][i-1][j-1]))+e[i][ii]+e[j][jj];if(i==j) dp[k][i][j]-=e[i][ii];}}}printf("%d\n",dp[n+m-1][n][n]);return 0;
}/*
2 2
1 2
2 1
*/

 

这篇关于矩阵取数问题 V2 51Nod - 1084的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---