[dynamic programming] p1004 grid access (four-dimensional DP template question)

The same method as passing a note ！

use f[i][j][k][l] The first person to come to (i,j), The second man came to (k,l) The best solution

We consider the Two people go at the same time , Equivalent to Digital triangle .

The equation of state transfer is ：

f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k-1][l],f[i][j-1][k][l-1])+a[i][j]+a[k][l];f[i][j][k][l]=max(f[i−1][j][k−1][l],f[i−1][j][k][l−1],f[i][j−1][k−1][l],f[i][j−1][k][l−1])+a[i][j]+a[k][l];

Because it can only be taken once , So when two people meet , Only add once , Otherwise, add two times （0 No impact ）

The two met ：i==k&&j==l

Code ：

#include<iostream>
using namespace std;
int n;
int a,b,c;
int G[100][100];
int dp[100][100][100][100];
void output(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<G[i][j]<<" ";
		}
		cout<<endl;
	}
}
int main(){
	cin>>n;
	cin>>a>>b>>c;
	while(!(a==0&&b==0&&c==0)){
		G[a][b]=c;
		cin>>a>>b>>c;
	} 
    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(max(dp[i-1][j][k-1][l],dp[i][j-1][k-1][l]),max(dp[i-1][j][k][l-1],dp[i][j-1][k][l-1]))+G[i][j]+G[k][l]*(i!=k&&j!=l);
				}
			}
		}
	}
	cout<<dp[n][n][n][n]; 
}