题目链接：https://www.dotcpp.com/oj/problem1639.html
题目描述
设有N*N的方格图(N< =10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。 某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出
只需输出一个整数，表示2条路径上取得的最大的和。
样例输入
8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0样例输出
67可以转化为两个人同时由A点走向B点所取得的最大的和。
dp[xi][yi][xj][yj]表示：其中一个人由（xi，yi）到B点，另一个人由（xj,yj）到B点所取得的最大的和。
注意：若两个人在同一点，该点的值只能加一次。
AC代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <string> #define cla(a, sum) memset(a, sum, sizeof(a)) #define rap(i, m, n) for(int i=m; i<=n; i++) #define rep(i, m, n) for(int i=m; i>=n; i--) #define bug printf("???\n") using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> P; typedef pair<ll, ll> Pl; const int Inf = 0x3f3f3f3f; const double eps = 1e-8; const int mod=998244353; const int maxn = 3e4; const int N=1e5; template <typename T> void read(T &x){ x = 0; int f = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();} while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } int n; int a[15][15]={0}; int dp[15][15][15][15]; int dfs(int xi,int yi,int xj,int yj){ if(xi<1||xi>n||yi>n||yi<1||xj<1||xj>n||yj<1||yj>n) return 0; if(xi==n&&yi==n&&xj==n&&yj==n)return a[xi][yi]; if(dp[xi][yi][xj][yj]!=-1)return dp[xi][yi][xj][yj];//剪枝 int t=a[xi][yi]; if(xi!=xj||yi!=yj)t+=a[xj][yj];//两个人在不同点 int x=0; //两个人有四种走法 x=max(x,dfs(xi+1,yi,xj+1,yj)); x=max(x,dfs(xi+1,yi,xj,yj+1)); x=max(x,dfs(xi,yi+1,xj+1,yj)); x=max(x,dfs(xi,yi+1,xj,yj+1)); dp[xi][yi][xj][yj]=x+t;//更新值 return dp[xi][yi][xj][yj]; } int main() { //ios::sync_with_stdio(false),cin.tie(0); read(n); int x,y,d; while(~scanf("%d%d%d",&x,&y,&d)&&(x||y||d)){ a[x][y]=d; } cla(dp,-1); printf("%d",dfs(1,1,1,1)); return 0; }
思路与记忆化搜索一样，只不过把搜索写为dp。
#include <iostream> using namespace std; const int N = 15; int w[N][N]; int f[N][N][N][N]; int main() { int n; cin >> n; int a, b, c; while(cin >> a >> b >> c, a || b || c) w[a][b] = c; for (int x1 = 1; x1 <= n; x1 ++) for (int y1 = 1; y1 <= n; y1 ++) for (int x2 = 1; x2 <= n; x2 ++) for (int y2 = 1; y2 <= n; y2 ++) { if(x1 + y1 != x2 + y2) continue;//走的步数要一样 int t = w[x1][y1]; if(x1 != x2 || y1 != y2) t += w[x2][y2]; int &x = f[x1][y1][x2][y2]; x = max(x, f[x1 - 1][y1][x2 - 1][y2] + t); x = max(x, f[x1 - 1][y1][x2][y2 - 1] + t); x = max(x, f[x1][y1 - 1][x2 - 1][y2] + t); x = max(x, f[x1][y1 - 1][x2][y2 - 1] + t); } cout << f[n][n][n][n] << endl; return 0; }
f[k][x1][x2]
集合：所有从（1， 1）开始，分别走到（x1， k - x1），（x2，k - x2）的方案的集合属性：最大值k：当前的横纵坐标之和
#include <iostream> using namespace std; const int N = 15; int w[N][N]; int f[N + N][N][N]; int main() { int n; cin >> n; int a, b, c; while(cin >> a >> b >> c, a || b || c) w[a][b] = c; for (int k = 2; k <= n + n; k ++) for (int x1 = 1; x1 < k; x1 ++) for (int x2 = 1; x2 < k; x2 ++) { int y1 = k - x1, y2 = k - x2; if(y1 < 1 || y1 > n || y2 < 1 || y2 > n) continue; int t = w[x1][y1]; if(x1 != x2) t += w[x2][y2]; int &x = f[k][x1][x2]; x = max(x, f[k - 1][x1 - 1][x2 - 1] + t); x = max(x, f[k - 1][x1 - 1][x2] + t); x = max(x, f[k - 1][x1][x2 - 1] + t); x = max(x, f[k - 1][x1][x2] + t); } cout << f[n + n][n][n] << endl; return 0; }