AcWing 1027. 方格取数
原题链接
简单
作者:
吕建威_7
,
2021-01-23 13:44:11
,
所有人可见
,
阅读 249
算法1
(三维DP) $O(n^3)$
C++ 代码
#include <iostream>
using namespace std;
const int N = 12;
int a[N][N], dp[2 * N][N][N];
int main()
{
int n;
cin >> n;
int r, c, w;
while (scanf("%d%d%d", &r, &c, &w), r || c || w) {
a[r][c] = w;
}
for (int k = 2; k <= 2 * 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 || j2 < 1 || j1 > n || j2 > n)
continue;
int t = a[i1][j1];
if (i1 != i2) {
t += a[i2][j2];
}
int &x = dp[k][i1][i2];
x = max(x, dp[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, dp[k - 1][i1][i2 - 1] + t);
x = max(x, dp[k - 1][i1 - 1][i2] + t);
x = max(x, dp[k - 1][i1][i2] + t);
}
}
}
cout << dp[2 * n][n][n] << endl;
return 0;
}