传送门：点击打开链接
题意：给一个矩阵，，刚开始两个点都在(1,1)，然后一起出发，只能向右走或者向下走，只能在(n,n)汇合，在到终点之前两个不能在同一个格子内，得分就是两条路径的数字之和。求得分最大。
因为数据比较小，所以可以直接开一个dp[x1][y1][x2][y2]来表示一个点在(x1,y1)另一个点在(x2,y2)时的最大得分
然后利用记忆化搜索递推就能得到答案了
#include<map>#include<set>#include<cmath>#include<stack>#include<queue>#include<cstdio>#include<string>#include<vector>#include<cstring>#include<iostream>#include<algorithm>#include<functional>#define FIN freopen("input.txt","r",stdin)#define FOUT freopen("output.txt","w+",stdout)using namespace std;typedef long long LL;typedef pair<int, int> PII;const int MX = 30 + 5;int n;int dp[MX][MX][MX][MX], A[MX][MX];int DP(int x1, int y1, int x2, int y2) {int &d = dp[x1][y1][x2][y2];if(d) return d;if(x1 > 1) d = max(d, DP(x1 – 1, y1, x2 – 1, y2));if(y2 > 1) d = max(d, DP(x1, y1 – 1, x2, y2 – 1));if(x1 > 1 && y2 > 1) d = max(d, DP(x1 – 1, y1, x2, y2 – 1));if(!(y1 – 1 == y2 && x2 – 1 == x1)) d = max(d, DP(x1, y1 – 1, x2 – 1, y2));d += A[x1][y1] + A[x2][y2];return d;}int main() {//FIN;while(~scanf("%d", &n)) {memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {scanf("%d", &A[i][j]);}}printf("%d\n", DP(n – 1, n, n, n – 1) + A[1][1] + A[n][n]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
不曾见谁。则见朵花儿闪下来，好一惊。
