To boldly go where no one has gone before.

【学习笔记】四维dp

2019-09-04 23:11:21


四维dp

四维dp可以用来解决在行走方向固定的情况下,在一个矩阵内从$(1,1)$到$(n,m)$的两条不同路径的某些信息。


例题 P1004

分析

题面意思是给出一个$n\times n$的矩阵,从$(1,1)$开始取数,每次只能向右走或者向下走,数被取走后就没有了,求两次取数能够得到的最大和。

这就是 四维dp

用$f[i][j][k][l]$表示第一次走到$(i,j)$,第二次走到$(k,l)$时能获得的最大和,那么由于只能向右走和向下走,所以每种状态仅有四种可能的前驱。所以转移方程就可以写成:

$$f[i][j][k][l]=max\{f_{pre}\}+a[i][j]+a[k][l]$$

特别地,如果$i=k$且$j=l$,则$f[i][j][k][l]$需要减去$a[i][j]$(每个数被取以后就变成$0$了)。

最终,在$f[n][n][n][n]$处获得答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10;
int n;
ll a[MAXN][MAXN], f[MAXN][MAXN][MAXN][MAXN];

int main() {
    scanf("%d", &n);
    for(int x = 1, y; x; ) {
        scanf("%d %d", &x, &y);
        scanf("%lli", &a[x][y]);
    }
    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++) {
                    f[i][j][k][l] = max(
                     max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]),
                     max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1])
                     ) + a[i][j] + a[k][l];
                    if(i == k && j == l)
                        f[i][j][k][l] -= a[i][j];
                }
    printf("%lld", f[n][n][n][n]);
    return 0;
}

例题 P1006

分析

题面意思是给出一个$n\times m$的矩阵,需要找出从$(1,1)$到$(n,m)$的两条不重合路径。

和 P1004 非常相似,也可以用四维 dp 来解决这道题(好像实际上可以优化到三维,不过我还是算了)。这道题和 P1004 的不同之处在于,P1004 是每个格子可以走多次,而这道题每个格子只能走一次。

其实这两种情况并没有什么区别,同样用$f[i][j][k][l]$表示走到$(i,j)$和$(k,l)$能得到的最大好感度。因为对于$i=k$且$j=l$的情况,将$f[i][j][k][l]$减去$a[i][j]$即表示第二次经过$(i,j)$没有意义,也就是获得的好感度为$0$。可以发现第二条路经任何不同于$(i,j)$的方格都能比经过$(i,j)$更优,那么这种状态在转移过程中自然就被舍弃掉了。所以,这里使用和 P1004 相同解法的正确性是显然的,可以直接无脑进行四维dp。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 60;
int n, m;
ll a[MAXN][MAXN], f[MAXN][MAXN][MAXN][MAXN];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) 
            scanf("%lli", &a[i][j]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int k = 1; k <= n; k++)
                for(int l = 1; l <= m; l++) {
                    f[i][j][k][l] = max(
                        max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]),
                        max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1])
                    ) + a[i][j] + a[k][l];
                    if(i == k && j == l)
                        f[i][j][k][l] -= a[i][j];
                }
    printf("%lli", f[n][m][n][m]);
    return 0;
}