P1004 方格取数

نُشر في

题目:P1004 方格取数

一个死亡四维dp

$dp[a][b][c][d]$代表第一个人走到$m[a][b]$第二人走到$m[c][d]$时的最大值

转移方程如下:

$$
dp[a][b][c][d]=max(\dp[a-1][b][c-1][d],\dp[a-1][b][c][d-1],\dp[a][b-1][c-1][d],\dp[a][b-1][c][d-1]) \+m[a][b]+m[c][d]
$$
但是要注意当$a==c\space and\space b==d$时,由于这个格子被加了两次要减去一个

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
using namespace std;
int dp[13][13][13][13];
int m[13][13],n;
int q,w,e=1;
int main()
{
	cin>>n;
	while(q!=0||w!=0||e!=0)
	{
		cin>>q>>w>>e;
		m[q][w]=e;
	}
	for(int a=1;a<=n;a++)
		for(int b=1;b<=n;b++)
			for(int c=1;c<=n;c++)
				for(int d=1;d<=n;d++)
				{
					dp[a][b][c][d]=
						max(dp[a-1][b][c-1][d],max(dp[a-1][b][c][d-1],max(dp[a][b-1][c-1][d],dp[a][b-1][c][d-1])))+m[a][b]+m[c][d];
					if(a==c&&b==d) dp[a][b][c][d]-=m[a][b];
				}
	cout<<dp[n][n][n][n];
	return 0;
 }