方格取数(动态规划)
作者:
amagi
,
2023-06-04 19:05:22
,
所有人可见
,
阅读 116
#include <iostream>
using namespace std;
const int N = 15;
int m,n;
int x[N][N];
int f[N * N][N][N];
int main(){
cin >> m;
for(int i = 1; i <= m; i ++){
int a,b,c;
cin >> a >> b >> c;
x[a][b] = c;
}
int kk,ff,gg;
cin >> kk >> ff >> gg;
for(int k = 2; k <= m + m; k ++){
for(int x1 = max(1,k - m); x1 <= min(k - 1,m); x1 ++){
for(int x2 = max(1,k - m); x2 <= min(k - 1,m);x2 ++){
int t = x[x1][k - x1];
if(x1 != x2) t += x[x2][k - x2];
for(int a = 0; a <= 1; a ++)
for(int b = 0; b <= 1; b ++)
f[k][x1][x2] = max(f[k][x1][x2],f[k - 1][x1 - a][x2 - b] + t);
}
}
}
cout << f[m + m][m][m] << endl;
}