侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【动态规划】方格取数 「动态规划之数字三角形模型」

GabrielxD
2023-02-09 / 0 评论 / 0 点赞 / 102 阅读 / 1,965 字
温馨提示:
本文最后更新于 2023-02-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1027. 方格取数 - AcWing题库


设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:

2.gif

某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。

在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。

此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。

输入格式

第一行为一个整数N,表示 N×N 的方格图。

接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。

行和列编号从 11 开始。

一行“0 0 0”表示结束。

输出格式

输出一个整数,表示两条路径上取得的最大的和。

数据范围

N10N \le 10

输入样例:

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出样例:

67

解题

方法一:动态规划 数字三角形模型

错误思路

为什么不能先走第一次求出最大值并记录最优路径,然后把路径上的点清零后再走第二次最优路线?

因为:第一次走虽然为局部最优但是对第二次走造成了影响,这就导致第二次走是在第一次影响下所能走的局部最优,不具备「无后效性」,因此分开两次走并不是全局最优解。

例如:

0 1 0
2 2 2
1 0 0

这样的测试用例,在第一次走时一定会把所有的 22 都拿完以得到最优路径,第二次走就只能拿到一个 11 了。
而第一次走不追求局部最优解是可以把图中所有数给拿完的。

错误代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 15;
    static int[][] g = new int[N][N], f = new int[N][N];
    static boolean[][] prevs = new boolean[N][N];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (true) {
            in.nextToken();
            int i = (int) in.nval;
            if (i == 0) break;
            in.nextToken();
            int j = (int) in.nval;
            in.nextToken();
            int x = (int) in.nval;
            g[i][j] = x;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (f[i - 1][j] > f[i][j - 1]) {
                    f[i][j] = f[i - 1][j] + g[i][j];
                    prevs[i][j] = true;
                } else f[i][j] = f[i][j - 1] + g[i][j];
            }
        }
        int ans = f[n][n];
        for (int i = n, j = n; i > 0 && j > 0;) {
            g[i][j] = 0;
            if (prevs[i][j]) --i;
            else --j;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]) + g[i][j];
            }
        }
        System.out.println(ans + f[n][n]);
    }
}

正确思路

只走一次的题目的基础上延伸,首先考虑用 f(x1,y1,x2,y2)f(x_1, y_1, x_2, y_2) 表示所有第一次从 (1,1)(1, 1) 走到 (x1,y1)(x_1, y_1) ,第二次从 (1,1)(1, 1) 走到 (x2,y2)(x_2, y_2) 的所有路径中取得数字和的最大值

在上面的错误思路中我们发现不能分开考虑两次走的路径,所以尝试两次一起走,那么就需要在求最优路径的基础上同时判断「同一个格子不能被重复选择」极了。

由于每次只能向下或向右行走,不能回头,那么只有在两次走到同一步时才有机会选择到同一个格子,也就是说只有在 x1+y1=x2+y2x_1+y_1 = x_2+y_2 时,两条路径选择的格子才有可能重合,因此可以把路径长度作为 DP 的阶段,每个阶段中,我们同时把两条路径扩展一步(即路径长度加 11 ),来进入下一个阶段。

综上所述,使用 f(k,x1,x2)f(k, x_1, x_2) 表示所有第一次从 (1,1)(1, 1) 走到 (x1,kx1)(x_1, k - x_1) ,第二次从 (1,1)(1, 1) 走到 (x2,kx2)(x_2, k - x_2) 的所有路径中取得数字和的最大值,其中 k=x1+y1=x2+y2k = x_1+y_1=x_2+y_2

于是,动态规划的初始状态为:f(2,1,1)f(2, 1, 1) ,目标状态为: f(2n,n,n)f(2n, n, n)

对于如何判断两次路径选择了同一个方格,由于每个阶段两条路线所选点的横纵坐标和相同,若横坐标相同,则纵坐标必相同,故使用 x1=x2x_1 = x_2 来判断:

  • x1=x2x_1 = x_2 时,两路线选格相同,只取一次 g[x1][y1]g[x_1][y_1] 即可。
  • x1x2x_1 \ne x_2 时,两路线选格不同,g[x1][y1]g[x_1][y_1]g[x2][y2]g[x_2][y_2] 都要取到。

总结:

  • 状态定义:f[k][i1][i2]f[k][i_1][i_2] 表示所有第一次从 (1,1)(1, 1) 走到 (i1,ki1)(i_1, k - i_1) ,第二次从 (1,1)(1, 1) 走到 (i2,ki2)(i_2, k - i_2) 的所有路径中取得数字和的最大值

  • 状态转移方程:

    f[k][i1][i2]=max(max(f[k1][i11][i21],f[k1][i1][i2]),max(f[k1][i1][i21],f[k1][i11][i2]))+{g[i1][k  i1]i1 = i2g[i1][k  i1] + g[i2][k  i2]i1  i2f[k][i_1][i_2] =\max(\max(f[k - 1][i_1 - 1][i_2 - 1], f[k - 1][i_1][i_2]), \max(f[k - 1][i_1][i_2 - 1], f[k - 1][i_1 - 1][i_2])) + \begin{cases} g[ i_{1}][ k\ -\ i_{1}] & i_{1} \ =\ i_{2}\\ g[ i_{1}][ k\ -\ i_{1}] \ +\ g[ i_{2}][ k\ -\ i_{2}] & i_{1} \ \neq \ i_{2} \end{cases}

  • 初始状态:f[2][1][1]=g[1][1]f[2][1][1] = g[1][1]

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 15;
    static int[][] g = new int[N][N];
    static int[][][] f = new int[N * 2][N][N];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (true) {
            in.nextToken();
            int i = (int) in.nval;
            if (i == 0) break;
            in.nextToken();
            int j = (int) in.nval;
            in.nextToken();
            int x = (int) in.nval;
            g[i][j] = x;
        }
        for (int k = 2; k <= n + n; ++k) {
            for (int i1 = 1; i1 <= n; ++i1) {
                for (int i2 = 1; i2 <= n; ++i2) {
                    int j1 = k - i1, j2 = k - i2;
                    if (j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue;
                    int t = g[i1][j1];
                    if (i1 != i2) t += g[i2][j2];
                    f[k][i1][i2] = Math.max(Math.max(f[k - 1][i1 - 1][i2 - 1], f[k - 1][i1][i2]),
                        Math.max(f[k - 1][i1][i2 - 1], f[k - 1][i1 - 1][i2])) + t;
                }
            }
        }
        System.out.println(f[n * 2][n][n]);
    }
}
0

评论区