題目連結: https://zerojudge.tw/ShowProblem?problemid=d109
# 內容
纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)，小轩坐在矩阵的右下角，坐标 (m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。
全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 0 表示），可以用一个 0-100 的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径
# 解題思路
因為 m,n 的最大數只有到 50，就用最硬的方法做吧
用四維的 DP 爆做吧～～
# 程式碼
#include<bits/stdc++.h> | |
using namespace std; | |
int dp[51][51][51][51]={}; | |
int main(){ | |
int m,n; | |
cin>>m>>n; | |
int _map[m+1][n+1]; | |
for(int i = 1;i<=m;i++) | |
for(int j = 1;j<=n;j++) | |
cin>>_map[i][j]; | |
int maxi = 0; | |
for(int i=1;i<=m;i++) | |
for(int j=1;j<=n;j++) | |
for(int k=1;k<=m;k++) | |
for(int l=1;l<=n;l++) | |
{ | |
maxi=max(max(dp[i-1][j][k][l-1],dp[i][j-1][k][l-1]),max(dp[i-1][j][k-1][l],dp[i][j-1][k-1][l])); | |
dp[i][j][k][l]=maxi+_map[i][j]; | |
if(i!=k||j!=l) | |
dp[i][j][k][l]+=_map[k][l]; | |
} | |
cout<<dp[m][n][m][n]; | |
return 0; | |
} |
