[南海云课堂] [DP] 最大价值

_Cheems · 2023-08-16 20:19:48 · 个人记录

洛谷链接

题意

输入一个 n*n 的矩形，每个 a_{i,j} 是这个位置的价值。现在要从左上角走到右下角再返回，每个价值只被计算一次，求最大价值和

思路

首先进行问题转换，可视作两个人同时从起点走向终点，每个点价值只被计算一次。

那便得到关键性质 同时，启发我们将两个人放在一起计算。

那么易想到暴力 \rm{DP}，令 f_{i,j,x,y} 表示第一个人在 (i,j)、第二个人在 (x,y) 时的最大价值和，时空复杂度都是 O(n^4)。

考虑优化，观察到 i,j,x,y 中有一维是多余的。例如 y=i+j-x，这样便能优化掉一维。

再次整理思路，上一种方法可做但不清晰，不妨设 f_{step,i,x} 表示当前进行到第 step 步，且二人的横坐标分别为 i,x 时的最大价值。

这样做时空复杂度是 O(n^3)，可过。

考试时愣是没任何思路，这个故事告诉我们先写暴力是好习惯。

代码

价值可能为负，要注意初始化，以及坐标是否出界。

主要部分就在这：

for(int step=1; step<=2*n-1;step++){
        for(int i=1; i<=n;i++){
            for(int x=1; x<=n;x++){
                int j=step-i+1,y=step-x+1;
                if(j<1||j>n) continue;
                if(y<1||y>n) continue;
                f[step][i][x]=max(f[step-1][i-1][x-1],f[step][i][x]);
                f[step][i][x]=max(f[step-1][i][x-1],f[step][i][x]);
                f[step][i][x]=max(f[step-1][i-1][x],f[step][i][x]);
                f[step][i][x]=max(f[step-1][i][x],f[step][i][x]);
                f[step][i][x]+=a[i][j]+a[x][y];
                if(i==x&&j==y){
                    f[step][i][x]-=a[i][j];
                }
            }
        }
    }