一个地图走两次,求两次路径的取物品价值最大问题
#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;
while (cin >> a >> b >> c)w[a][b] = c;
//因为从(1,1)开始 k=1+1=2
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;
int 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[n + n][n][n] << endl;
return 0;
}