发布于 

【LG1004】方格取数 题解

这是一道四维DP的模版题,思维难度也不大,题目链接here

核心思路

定义dp[i][j][k][l]dp[i][j][k][l]为第一次走到(i,j)(i,j)第二次走到(k,l)(k,l)的最优方案,a[i][j]a[i][j]为放在(i,j)(i,j)处的数字。

由于每一步只能从i1i-1j1j-1k1k-1l1l-1转移

状态转移方程就很好推出了:

dp[i][j][k][l]=max(dp[i1][j][k1][l],max(dp[i][j1][k1][l],dp[i][j1][k][l1],dp[i1][j][k][l1])++a[i][j]+a[k][l]dp[i][j][k][l]=\max(dp[i-1][j][k-1][l],max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1],dp[i-1][j][k][l-1])++a[i][j]+a[k][l]

要尤其注意(i,j)(i,j)(k,l)(k,l)相同的情况

完整代码

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
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;

#define MAXN 10+5

int read() {
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int dp[MAXN][MAXN][MAXN][MAXN],a[MAXN][MAXN];

int main() {
int n=read();
while(1) {
int x,y,s;
x=read(),y=read(),s=read();
if(x==0&&y==0&&s==0) break;
a[x][y]=s;
}
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],max(dp[i][j-1][k-1][l],max(dp[i][j-1][k][l-1],dp[i-1][j][k][l-1])))+a[i][j]+a[k][l];

if(i==k&&j==l) dp[i][j][k][l]-=a[i][j];
}

printf("%d",dp[n][n][n][n]);
}