方格取数 题解

看到这道题很容易想到动态规划，求一个矩阵最大权值路径算是家常便饭了
但是它要求输出的是两条路线和最大 这就有点伤脑筋了。。。
在做一条路线的时候我们是定义二维$DP[i][j]$，表示路线在$(i,j)$位置上所能获得的最大值
现在多了一条路线，多了两个状态，那我们再加两维让它变成四维$DP$和二维的时候差不多求解，这不就解决了嘛！
定义$DP[i][j][w][k]$表示第一条路线在$(i,j)$,第二条路线在$(w,k)$时的最大取值 使用四个$for$循环(毕竟数据不大)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll a[15][15];//存储方格上的数 
ll DP[15][15][15][15];//存储第一条路线在(i,j),第二条路线在(w,k)时的最大取值 
ll maxn(ll x,ll y){return x>y?x:y;}//最大值 
int main(){
	cin>>n;
	int x,y,t;
	do{
		cin>>x>>y>>t;
		a[x][y]=t;
	}while(x!=0&&y!=0&&t!=0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int w=1;w<=n;w++){
				for(int k=1;k<=n;k++){
					//对于一次新状态可由四种上一状态得出:上上 左上 上左 左左 
					ll t1=DP[i-1][j][w-1][k];//上上 
					ll t2=DP[i][j-1][w-1][k];//左上 
					ll t3=DP[i-1][j][w][k-1];//上左 
					ll t4=DP[i][j-1][w][k-1];//左左
					if(i==w&&j&&k){//如果两条路线取得同一个格子 
						DP[i][j][w][k]=maxn(t1,maxn(t2,maxn(t3,t4)))+a[i][j];//上一状态的最大值+当前格子 
					} 
					else{
						DP[i][j][w][k]=maxn(t1,maxn(t2,maxn(t3,t4)))+a[i][j]+a[w][k];
						//上一状态的最大值+两条路线分别取的新格子 
					}
				}
			}
		}
	}
	cout<<DP[n][n][n][n];
	return 0;
}