AcWing 1027. 提高课_动态规划_方格取数
原题链接
简单
作者:
我需要0失误
,
2022-07-05 10:30:17
,
所有人可见
,
阅读 113
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11;
int w[N][N];
int f[N][N][N][N];
int main()
{
int n;
cin>>n;
int x,y,z;
while((cin>>x>>y>>z)&&(x||y||z)){
w[x][y]=z;
}
for(int i1=1;i1<=n;i1++)
for(int j1=1;j1<=n;j1++)
for(int i2=1;i2<=n;i2++)
for(int j2=1;j2<=n;j2++)
{
int temp;
if(i1==i2&&j1==j2)
temp = w[i1][j1];
else
temp = w[i1][j1] + w[i2][j2];
int &x = f[i1][j1][i2][j2];
x = max(x,f[i1-1][j1][i2-1][j2]+ temp);
x = max(x,f[i1-1][j1][i2][j2-1]+ temp) ;
x = max(x,f[i1][j1-1][i2-1][j2]+ temp) ;
x = max(x,f[i1][j1-1][i2][j2-1]+ temp) ;
}
cout<<f[n][n][n][n];
return 0;
}