AcWing 1027. 方格取数
原题链接
简单
作者:
Jacky.C
,
2021-01-12 20:28:20
,
所有人可见
,
阅读 2
C++ 代码
#include<iostream>
#include<cmath>
#include<string.h>
using namespace std;
int dp(int map[][15], int n)
{
int f[30][15][15];
memset(f,0,sizeof(f));
f[0][0][0] = map[0][0];
for(int k = 2; k < 2*n+1; k++){
for(int i1 = 1; i1 <= n; i1++){
for(int i2 = 1; i2 <= n; i2++){
int j1 = k - i1, j2 = k - i2;
if(j1 > 0 && j1 <= n && j2 > 0 && j2 <= n){
int mm = 0;
int v = (i1 == i2)? map[i1][j1] : map[i1][j1] + map[i2][j2];
mm = max(mm, f[k-1][i1][i2] + v);
mm = max(mm, f[k-1][i1-1][i2] + v);
mm = max(mm, f[k-1][i1][i2-1] + v);
mm = max(mm, f[k-1][i1-1][i2-1] + v);
f[k][i1][i2] = mm;
}
}
}
}
return f[2*n][n][n];
}
int main()
{
int n,x,y,v;
int map[15][15];
for(int i = 0; i < 15; i++){
for(int j = 0; j < 15; j++){
map[i][j] = 0;
}
}
cin>>n;
while(cin>>x>>y>>v, x&&y&&v){
map[x][y] = v;
}
cout<<dp(map, n)<<endl;
return 0;
}