基準時間限制：2 秒 空間限制：131072 KB 分值: 80 難度：5級算法題
收藏
關注一個M*N矩陣中有不同的正整數，經過這個格子，就能獲得相應價值的獎勵，先從左上走到右下，再從右下走到左上。第1遍時只能向下和向右走，第2遍時只能向上和向左走。兩次如果經過同一個格子，則該格子的獎勵只計算一次，求能夠獲得的最大價值。 例如：3 * 3的方格。1 3 32 1 32 2 1能夠獲得的最大價值為：17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起點和終點的獎勵只計算1次。Input第1行：2個數M N，中間用空格分隔，為矩陣的大小。(2 <= M, N <= 200)第2 - N + 1行：每行M個數，中間用空格隔開，對應格子中獎勵的價值。(1 <= A[i,j] <= 10000)Output輸出能夠獲得的最大價值。Input示例3 31 3 32 1 32 2 1Output示例17
#include<cstdio>#include<iostream>#define MAX(a,b,c,d) max(max(a,b),max(c,d))using namespace std;int n,m,a[201][201],dp[401][201][201]={0};int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int k=2;k<=n+m;k++) for(int i=1;i<=n&&k-i>0;i++) for(int j=1;j<=n&&k-j>0;j++) dp[k][i][j]=max(dp[k][i][j], MAX(dp[k-1][i][j],dp[k-1][i-1][j-1],dp[k-1][i-1][j],dp[k-1][i][j-1])+a[i][k-i]+(i==j?0:a[j][k-j])); PRintf("%d/n",dp[n+m][n][n]); return 0;}
新聞熱點
疑難解答
