方格取数

动态规划，数字三角形模型

题目链接

https://www.luogu.com.cn/problem/P1004

题目描述

解法一 $O(n^4)$

#include<bits/stdc++.h>
using namespace std;
int n, i, j, l, k, x, y, s;
int d[55][55], f[55][55][55][55];
int main() 
{cin>>n;while(cin>>x>>y>>s && x)d[x][y] = s;for(i = 1; i <= n; i++)for(j = 1; j <= n; j++)for(l = 1; l <= n; l++)for(k = 1; k <= n; k++) {//四种走法，右 和 下 的四种组合f[i][j][l][k] = max(max(f[i - 1][j][l - 1][k], f[i][j - 1][l][k-1]), max(f[i - 1][j][l][k - 1], f[i][j - 1][l - 1][k])) + d[i][j];//若是两个走到同一个位置，因为走过的会变0，故只需+一次，不同的话则两个值都得加if(i != 1 && j != k) f[i][j][l][k] += d[l][k];}printf("%d", f[n][n][n][n]);return 0;

解法二 $O(n^3)$

//走两次
//f[i1, j1, i2, j2]表示所有从(1,1),(1,1)分别走到(i1, j1), (i2,j2)
//这里因为我们最后需要走到同一个格子，故可以优化为三维(k, i1, i1)，k = i1 + j1 = i2 + j2 
//注意i1和i2可能相同，则根据情况不同所加权值也不同
//最终要求的答案为f[n + n][n][n] 
#include <iostream>
#include <algorithm> 
using namespace std;
const int N = 15;
int n;
int w[N][N], f[N * 2][N][N];	//k,i1,i2int main() {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 i1 = 1; i1 <= n; i1 ++) {for(int i2 = 1; i2 <= n; i2 ++) {int j1 = k - i1, j2 = k - i2;if(j1 < 1 || j1 >n || j2 < 1 || j2 > n)	continue;int value = w[i1][j1];if(i1 != i2)	value += w[i2][j2];int y1 = f[k - 1][i1 - 1][i2 - 1] + value;//右右 int y2 = f[k - 1][i1][i2 - 1] + value;//下右 int y3 = f[k - 1][i1 - 1][i2] + value;//右下 int y4 = f[k - 1][i1][i2] + value;//下下 f[k][i1][i2] = max({y1, y2, y3, y4});}}}	cout << f[n + n][n][n] << endl;return 0;
}