You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

38 lines
1.5 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n;
int w[N][N];
int f[N * 2][N][N];
int main() {
cin >> n;
// 接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
int a, b, c;
// 一行 0 0 0 表示结束。
while (cin >> a >> b >> c, a || b || c) w[a][b] = c;
// k表示两个小朋友所在位置的x+y的和最多是2*n
for (int k = 2; k <= 2 * n; k++)
for (int x1 = 1; x1 <= n; x1++) // 第一个小朋友竖着走的距离
for (int x2 = 1; x2 <= n; x2++) { // 第二个小朋友竖着走的距离
int y1 = k - x1, y2 = k - x2; // 计算横着走的距离
// 不能出界,只走有效的位置
if (y1 >= 1 && y1 <= n && y2 >= 1 && y2 <= n) {
// PK获取到最优的上一个状态
int t = f[k - 1][x1 - 1][x2];
t = max(t, f[k - 1][x1 - 1][x2 - 1]);
t = max(t, f[k - 1][x1][x2 - 1]);
t = max(t, f[k - 1][x1][x2]);
// 将本位置的数值加上
f[k][x1][x2] = t + w[x1][y1];
// 如果不是重复的位置,还可以继续加上
if (x1 != x2 && y1 != y2) f[k][x1][x2] += w[x2][y2];
}
}
// 输出DP的结果
printf("%d\n", f[2 * n][n][n]);
return 0;
}