参考《算法竞赛进阶指南》、AcWing题库

898. 数字三角形

题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

1
2
3
4
5
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数 nn，表示数字三角形的层数。

接下来 nn 行，每行包含若干整数，其中第 ii 行表示数字三角形第 ii 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤5001 \le n \le 500,
−10000≤三角形中的整数≤10000-10000 \le 三角形中的整数 \le 10000

输入样例：

1
2
3
4
5
6
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

1
30

Solution

自上而下
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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int a[N][N];
int f[N][N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            cin >> a[i][j];
        } 
    }
    memset(f, 0xc0, sizeof f);
    f[1][1] = a[1][1];
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];
        } 
    }
    int ans = 0xc0c0c0c0;
    for (int j = 1; j <= n; ++j) ans = max(ans, f[n][j]);
    cout << ans;
    return 0;
}
自下而上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
const int N = 510;
int a[N][N], f[N][N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            cin >> a[i][j];
        } 
    }
    for (int i = n; i >= 1; --i) {
        for (int j = i; j >= 1; --j) {
            f[i][j] = max(f[i + 1][j + 1], f[i + 1][j]) + a[i][j];
        } 
    }
    cout << f[1][1];
    return 0;
}

1015. 摘花生

题目描述

Hello Kitty 想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地 (如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty 只能向东或向南走，不能向西或向北走。

问 Hello Kitty 最多能够摘到多少颗花生。

输入格式

第一行是一个整数 T，代表一共有多少组数据。

接下来是 T 组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数 R 和列数 C。

每组数据的接下来 R 行数据，从北向南依次描述每行花生苗的情况。每行数据有 C 个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目 M。

输出格式

对每组输入数据，输出一行，内容为 Hello Kitty 能摘到得最多的花生颗数。

数据范围

1≤T≤1001 \le T \le 100,
1≤R,C≤1001 \le R,C \le 100,
0≤M≤10000 \le M \le 1000

输入样例：

1
2
3
4
5
6
7
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

输出样例：

1
2
8
16

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N],f[N][N];
int main() {
    int n;
    cin >> n;
    while (n -- ) {
        int r, c;
        cin >> r >> c;
        for (int i = 1; i <= r; ++i) {
            for (int j = 1; j <= c; ++j) {
                cin >> a[i][j];
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
            }
        }
        cout << f[r][c] << endl;
    }
}

1018. 最低通行费

题目描述

一个商人穿过一个 N×NN×N 的正方形的网格，去参加一个非常重要的商务活动。

他要从网格的左上角进，右下角出。

每穿越中间 11 个小方格，都要花费 11 个单位时间。

商人必须在 (2N−1)(2N-1) 个单位时间穿越出去。

而在经过中间的每个小方格时，都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。

请问至少需要多少费用？

注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

输入格式

第一行是一个整数，表示正方形的宽度 NN。

后面 NN 行，每行 NN 个不大于 100100 的正整数，为网格上每个小方格的费用。

输出格式

输出一个整数，表示至少需要的费用。

数据范围

1≤N≤1001 \le N \le 100

输入样例：

1
2
3
4
5
6
5
1  4  6  8  10
2  5  7  15 17
6  8  9  18 20
10 11 12 19 21
20 23 25 29 33

输出样例：

1
109

样例解释

样例中，最小值为 109=1+2+5+7+9+12+19+21+33109=1+2+5+7+9+12+19+21+33。

算法分析

这题一看很像爆搜啊，但是直接爆搜的时间复杂度是 2100002^{10000}，必然会超时

我们可以细看一下题目，总结一些性质出来

本题的起点是左上角的方块 (1,1)(1,1)，而终点是右下角的方块 (n,n)(n,n)

而每次移动，只能走到四相邻的格子中

四相邻：

我们常在一个矩阵中说四相邻，说的就是以当前格子为中心，上、下、左、右四个方向相邻的格子

也就是对于(x,y)(x,y)来说的(x−1,y),(x+1,y),(x,y−1),(x,y+1)(x-1,y),(x+1,y),(x,y-1),(x,y+1)的四个格子

因此，我们在矩阵中找任意两个点之间的距离，用到的不是欧式距离，而是曼哈顿距离

欧式距离：

在欧氏空间中，传统意义上的距离，do=(x1−x2)2+(y1−y2)2d_o = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}

曼哈顿距离：

两个点在标准坐标系上的绝对轴距总和，dm=∣x1−x2∣+∣y1−y2∣d_m = |x_1-x_2| + |y_1-y_2|

这题用的就是曼哈顿距离

我们可以模拟一下(1,1)(1,1)到(2,2)(2,2)的曼哈顿距离，答案是22

而我们从(1,1)(1,1)出发走到(2,2)(2,2)的最短距离路线分别是

(1,1)−>(1,2)−>(2,2)(1,1)->(1,2)->(2,2)或者(1,1)−>(2,1)−>(2,2)(1,1)->(2,1)->(2,2)，路线长度也是22

而对于起点的(1,1)(1,1)到终点(n,n)(n,n)，它们之间的曼哈顿距离是2n−22n - 2

而本题又要求我们在 2n−12n - 1 的时间内，从起点走到终点

因此，得出结论，我们的走的路线不是完全随机的，而是遵循最短路的原则走的

也就是说，每次移动，至少要使曼哈顿距离缩短 11

于是，规定了我们每次在不越过边界的情况下只能向右或向下移动

总结出该条性质以后，本题的模型就可以完全套用1015. 摘花生了

这题不同于摘花生的地方在于，他的属性是最小值，因此需要在代码上作出一点点改变

{状态表示f(i, j){属性:从起点出发，走到(i,j)位置的所有方案集合:方案中的路线经过的所有物品的总价值最小MIN状态转移f(i, j) = min{f(i - 1, j),f(i, j - 1)}+w(i, j)\begin{cases} \text{状态表示f(i, j)}\begin{cases} \text{属性:从起点出发，走到(i,j)位置的所有方案}\\ \text{集合:方案中的路线经过的所有物品的总价值最小MIN} \end{cases}\\ \text{状态转移f(i, j) = min\{f(i - 1, j),f(i, j - 1)\}+w(i, j)} \end{cases}

img

Solution

循环写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int w[N][N], f[N][N];
int main() {
    int n;
    cin >> n;
    memset(f, 0x3f, sizeof f);
    f[0][1] = f[1][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> w[i][j];
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
        }
    }
    cout << f[n][n];
}
记忆化搜索写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int a[N][N], f[N][N];
int dp(int x, int y) {
    if (f[x][y] != 0x3f3f3f3f) return f[x][y];//没有计算过
    if (x == 1 && y == 1) return a[x][y];//初始点
    if (x < 1 || y < 1) return f[x][y];//特判边界
    f[x][y] = min(dp(x - 1, y), dp(x, y - 1)) + a[x][y];//重要，这里转移的时候一定要写成调用dp函数的形式
    return f[x][y];
}
int main() {
    int n;
    cin >> n;
    f[0][1] = f[1][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }
    memset(f, 0x3f, sizeof f);
    cout << dp(n, n);
}

1027. 方格取数

题目描述

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

2.gif

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

在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

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

输入格式

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

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

行和列编号从 11 开始。

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

输出格式

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

数据范围

N≤10N \le 10

输入样例：

1
2
3
4
5
6
7
8
9
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

输出样例：

1
67

算法分析

看到题目，就会发现，又是一道数字三角形模型的题目

但不同以往，这次允许我们从起点出发两次，所以需要在原来的基础上做一些变形

关于当前的状态如何表示

一开始一般会想到用四维数组f[x1][y1][x2][y2]来记录两条路线当前走到位置的坐标

但是题目中有一个限制，那就是对于两次路线都经过的点，其价值只会被累加一次

如果用四个坐标来表示当前的状态，那我们还需要额外开一维来记录当前矩阵中哪些格子被取过数了

即 f[x1][y1][x2][y2][1 << (n * n)]

关于这种状态压缩的做法我就不再展开了，明眼人都看出来，时间复杂度和空间复杂度会爆掉

题目要求我们从起点先后出发两次

但我们可以规定两次是同时出发的，因为这两种方案的所有路线都是一一对应的

为什么这么映射呢？因为这样子做的话，我们可以轻松的处理两次路线走到同一个格子的情况

由此我们就可以把路径长度，作为DP的阶段

每个阶段中，我们同时把两条路径扩展一步，即路径长度加 11 ，来进入下一个阶段

而路径长度加11后，无非就是向下走一格或是向右走一格，对应横纵坐标的变换

根据k,x1,y1,x2,y2k,x_1,y_1,x_2,y_2的关系，我们可以获得如下等式

x1+y1=x2+y2=kx_1 + y_1 = x_2 + y_2 = k

获得上述等式以后，我们就可以通过三个维度来描述状态了，分别是k,x1,x2k, x_1, x_2

于是，状态的初值为f[2][1][1]，目标状态为f[2 * n][n][n]

则对于如何判断两次路线走进了同一个方格里，可以通过x1=x2x_1 = x_2来判断了

  1. 当x1≠x2x_1 \ne x_2，当前两条路线走到的格子不是同一个，则w=w(x1,k−x1)+w(x2,k−w2)\mathrm{w} = w(x_1,k-x_1) + w(x_2,k-w_2)
  2. 当x1=x2x_1=x_2，当前两条路线走到了同一个格子中，则w=w(x1,k−x1)\mathrm{w} = w(x_1,k-x_1)

而状态转移，基本参照数字三角形的模型即可

{状态表示fk,i,j{属性:路径长度为k,第一条路线到x1=i,第二条路线到x2=j的所有方案集合:方案中的路线经过的所有物品的总价值最大Max状态转移fk,i,j=max{fk−1,i,j,fk−1,i−1,j,fk−1,i,j−1,fk−1,i−1,j−1}+w\begin{cases} 状态表示f_{k,i,j} \begin{cases} 属性: 路径长度为k,第一条路线到x_1=i,第二条路线到x_2=j的所有方案 \\ 集合: 方案中的路线经过的所有物品的总价值最大 Max \end{cases} \\ 状态转移 f_{k,i,j} = max\{f_{k-1,i,j},f_{k-1,i-1,j},f_{k-1,i,j-1},f_{k-1,i-1,j-1}\} + w \end{cases}

IMG_623B17197D17-1.jpeg

Solution

三重循环迭代三个状态写法
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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int w[N][N], f[2 * N][N][N];
int main() {
    int n; 
    cin >> n;
    int x, y, num;
    while (cin >> x >> y >> num, x || y || num) {
        w[x][y] = num;
    }
    for (int k = 2; k <= 2 * n; ++k) {
        for (int x1 = 1; x1 <= n; ++x1) {
            for (int x2 = 1; x2 <= n; ++x2) {
                int y1 = k - x1, y2 = k - x2;
                if (y1 >= 1 && y1 <= n && y2 >= 1 && y2 <= n) {
                    int t = w[x1][y1];
                    if (x1 != x2) t += w[x2][y2];
                    f[k][x1][x2] = max({f[k - 1][x1 - 1][x2 - 1], f[k - 1][x1 - 1][x2], f[k - 1][x1][x2 - 1], f[k - 1][x1][x2]}) + t;
                }
            }
        }
    }
    cout << f[2 * n][n][n];
}
记忆化搜索写法
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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 15;
int w[N][N], f[2 * N][N][N];
int dp(int k, int x1, int x2) {
    if (f[k][x1][x2] != -1) return f[k][x1][x2];//已经计算出
    if (k < 2 || x1 < 1 || k - x1 < 1 || x2 < 1 || k - x2 < 1) return 0;//特判边界
    
    int t = w[x1][k - x1];
    if (x1 != x2) t += w[x2][k - x2];
    f[k][x1][x2] = max({dp(k - 1, x1 - 1, x2 - 1), dp(k - 1, x1 - 1, x2), dp(k - 1, x1, x2 - 1), dp(k - 1, x1, x2)}) + t;
	//注意是调用dp函数来更新当前点
    return f[k][x1][x2];
}
int main() {
    cin >> n;
    int x, y, num;
    while (cin >> x >> y >> num, x || y || num) {
        w[x][y] = num;
    }
    memset(f, -1, sizeof f);
    cout << dp(2 * n, n, n) << endl;
}

275. 传纸条

题目描述

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。

一次素质拓展活动中，班上同学安排坐成一个 mm 行 nn 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。

幸运的是，他们可以通过传纸条来进行交流。

纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)(1,1)，小轩坐在矩阵的右下角，坐标 (m,n)(m,n)。

从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。

班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 00 表示），可以用一个 0∼1000 \sim 100 的自然数来表示，数越大表示越好心。

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。

现在，请你帮助小渊和小轩找到这样的两条路径。

输入格式

第一行有 22 个用空格隔开的整数 mm 和 nn，表示学生矩阵有 mm 行 nn 列。

接下来的 mm 行是一个 m×nm \times n 的矩阵，矩阵中第 ii 行 jj 列的整数表示坐在第 ii 行 jj 列的学生的好心程度，每行的 nn 个整数之间用空格隔开。

输出格式

输出一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

数据范围

1≤n,m≤501 \le n,m \le 50

输入样例：

1
2
3
4
3 3
0 3 9
2 8 5
5 7 0

输出样例：

1
34

算法分析

image-20211104002635943

image-20211104002529428

这题明显不是一个裸题，我们需要一层一层的拆解分析

首先想到的是能不能往方格取数模型上靠

对于一个从 (n,m)(n,m) 出发到 (1,1)(1,1) 的路线，且只能向上或向右走，考虑将其方向调转，则必定对应一条从 (1,1)(1,1) 出发到 (n,m)(n,m) 的路线，且只能向下或向右走

IMG_DBF1CCEFA907-1.jpeg

这两种走法的方案都是一一对应的（即任意一条路线都可以找到其对应的反向路线），因此该方案映射合法

于是该问题就变成了寻找一条从 (1,1)(1,1) 出发到达 (n,m)(n,m)，每次只能向下或向右走，先后出发两次，且两次路线不能经过重复格子的最大价值方案

这样就很靠近方格取数模型了

关于如何解决不能经过重复格子的问题

我们先给定一个结论： 方格取数 dp模型的最优方案可以是不经过重复格子的

证明：

情况一：最优解的两条路线是相互交叉经过的

IMG_41A02C1923F3-1.jpeg

则我们可以对交叉出来的部分进行路线交换，如下图的操作

IMG_D04B2FA5BFB0-1.jpeg

于是，我们可以发现，所有的交叉路线都会映射成一种一条路线只在下方走，一条路线只在上方走的不交叉路线

因此我们只需集中解决情况二即可

情况二：最优解的两条路线不交叉，但在某些点有重合

IMG_91EF0191824B-1.jpeg

由于方格取数，对于走到相同格子时，只会累加一次格子的价值

于是我们可以使用贪心中的微调法来进行这部分的证明

对于重合的格子，我们必然可以在两条路线中找到额外的一条或两条路线，使得新的路线不发生重合

具体参照下图：

IMG_6202C63C2DFE-1.jpeg

由于原路线是最优解，则必然 wA=wB=0w_A = w_B = 0，否则最优解路线必然是经过 AA 或 BB 的

因此，我们可以通过微调其中的一条路线，使之不经过重合点 CC，同时路线的总价值没有减少

得证：最优解路线可以是不经过重复路线的

接下来就是完全参照方格取数的DP分析了

{状态表示fk,i,j{属性:路径长度为k,第一条路线到x1=i,第二条路线到x2=j的所有方案集合:方案中的路线经过的所有物品的总价值最大Max状态转移fk,i,j=max{fk−1,i,j,fk−1,i−1,j,fk−1,i,j−1,fk−1,i−1,j−1}+w\begin{cases} 状态表示f_{k,i,j} \begin{cases} 属性: 路径长度为k,第一条路线到x_1=i,第二条路线到x_2=j的所有方案 \\ 集合: 方案中的路线经过的所有物品的总价值最大 Max \end{cases} \\ 状态转移 f_{k,i,j} = max\{f_{k-1,i,j},f_{k-1,i-1,j},f_{k-1,i,j-1},f_{k-1,i-1,j-1}\} + w \end{cases}

IMG_623B17197D17-1.jpeg

状态的初值: f[2][1][1]

目标的状态: f[n + m][n][m]

Solution

等价方格取数，如果方格取数求出的最优解路线是有交点的，那么一定存在值相同的路线是不相交的，也是最优解
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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int m, n;
int w[N][N], f[2 * N][N][N];
int main() {
    cin >> m >> n;
    for (int i = 1; i <= m; ++i) 
        for (int j = 1; j <= n; ++j) cin >> w[i][j];
        
    for (int k = 2; k <= m + n; ++k) {
        for (int x1 = 1; x1 <= m; ++x1) {
            for (int x2 = 1; x2 <= m; ++x2) {
                int y1 = k - x1, y2 = k - x2;
                if (y1 >= 1 && y1 <= n && y2 >= 1 && y2 <= n) {
                    int t = w[x1][y1];
                    if (x1 != x2) t += w[x2][y2];
                    f[k][x1][x2] = max({f[k - 1][x1 - 1][x2 - 1], f[k - 1][x1 - 1][x2], f[k - 1][x1][x2 - 1], f[k - 1][x1][x2]}) + t;
                }
            }
        }
    }
    cout << f[m + n][m][m];
}
跳过重合点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int m, n;
int w[N][N], f[2 * N][N][N];
int main() {
    cin >> m >> n;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) cin >> w[i][j];
    for (int k = 2; k <= m + n; ++k) {
        for (int x1 = 1; x1 <= m; ++x1) {
            for (int x2 = 1; x2 <= m; ++x2) {
                int y1 = k - x1, y2 = k - x2;
                if (y1 < 1 || y1 > n || y2 < 1 || y2 > n) continue;
                if (x1 == x2 && k != m + n) continue;//不能重合，重合则跳过，f[重合点]=0，取max时不影响其他状态点。注意最后终点不跳过，要计算
                f[k][x1][x2] = max({f[k - 1][x1 - 1][x2 - 1], f[k - 1][x1 - 1][x2], f[k - 1][x1][x2 - 1], f[k - 1][x1][x2]}) + w[x1][y1] + w[x2][y2];
            }
        }
    }
    cout << f[m + n][m][m];
}