DP-方格取数

题目链接

方格取数

思路

用思维DP，dp[i][j][k][l]表示第一个点走到i,j,第二个点走到k,l的最大值。
然后根据转移，第一个点可以由左或者上转移，第二个点也是。那么一共有四种组合。
左左，上上，左上，上左。然后根据这两点的坐标是否相同，决定贡献。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll dp[11][11][11][11];
int mp[11][11];
int n; 
int main()
{
	scanf("%d",&n);
		int x,y,v;
		while(cin>>x>>y>>v)
        {
            if(x==0&&y==0&&v==0)break;
            mp[x][y]=v;
        }
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int k=1;k<=n;k++)
	for(int l=1;l<=n;l++)
	{
        dp[i][j][k][l]=max(dp[i-1][j][k-1][l],dp[i][j][k][l]);//左左 
        dp[i][j][k][l]=max(dp[i][j-1][k][l-1],dp[i][j][k][l]);//上上
		dp[i][j][k][l]=max(dp[i-1][j][k][l-1],dp[i][j][k][l]);//左上
		dp[i][j][k][l]=max(dp[i][j-1][k-1][l],dp[i][j][k][l]);//上左
		if(i==k&&j==l)dp[i][j][k][l]+=mp[i][j];
		else dp[i][j][k][l]+=(mp[i][j]+mp[k][l]); 
	}
	cout<<dp[n][n][n][n]<<endl;
}