【LG1004】方格取数 题解
这是一道四维DP的模版题，思维难度也不大，题目链接here
核心思路
定义dp[i][j][k][l]为第一次走到(i,j)第二次走到(k,l)的最优方案，a[i][j]为放在(i,j)处的数字。
由于每一步只能从i−1、j−1、k−1、l−1转移
状态转移方程就很好推出了：
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)和(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]);
}
|
