题目描述
此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。
样例
数据范围
N≤10
输入样例:
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
算法
(暴力枚举) $O(n^3)$
k表示一条路径走过的总共步数。
即:
k = i + j;
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 15;
int n;
int w[N][N], f[2 * N][N][N];
int main()
{
cin >> n;
int a, b, c;
while (cin >> a >> b >> c, a || b || c)
{
w[a][b] = c;
}
for (int k = 2; k <= 2 * n; k ++ ) // k 是一条路径的总步数,即i1 + j1 == 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)
{
int t = w[i1][j1];
if (i1 != i2) t += w[i2][j2];
int &x = f[k][i1][i2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2] +t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2] + t);
}
}
cout << f[2 * n][n][n] << endl;
return 0;
}