AcWing 1027. 方格取数
原题链接
简单
作者:
wangyj
,
2021-01-11 17:12:48
,
所有人可见
,
阅读 269
#include<iostream>
#include<algorithm>
using namespace std;
int n,w[15][15],f[30][15][15],a,b,c,k,i1,i2,j1,j2,t;
int main()
{
scanf("%d",&n);
while(cin>>a>>b>>c,a||b||c)w[a][b]=c;
for(k=2;k<=n+n;k++)
for(i1=1;i1<=n;i1++)
for(i2=1;i2<=n;i2++){
j1=k-i1,j2=k-i2;
if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
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);
}
}
printf("%d\n",f[n+n][n][n]);
return 0;
}