1018.最低通行费

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

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

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

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

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

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

请问至少需要多少费用？

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

输入格式

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

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

输出格式

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

数据范围

$1 \le N \le 100$

观察题意，发现就是DP

可以参考这一篇题解的动规思路 1015.摘花生

直接写dp方程：

状态表示

$f[i][j]$ 表示从左下角到位置 $[i, j]$ 的最小值

状态转移

很明显，枚举顺序是先行后纵

所以，$[i, j]$ （只能）依赖于 $[i - 1, j]$ 和 $[i, j - 1]$

也就是，f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w;

而第 i 层的答案只依赖于第 i 层和第 i - 1 层，容易想到滚动数组优化

在看到方程，发现不用滚动数组，直接用一维存即可（具体解释见代码）

一维转移：f[j] = max(f[j], f[j - 1]) + w;

答案表示

用二维存就是 f[n][m]

用一维存就是 f[m]

注意这道题是求最小值，所以要注意边界条件

c++代码

#include <bits/stdc++.h>

using namespace std;

const int N = 109;

int n;                                            //正方形的宽度
int f[N];                                         //f[i][j] 表示从坐标 [1, 1] 到坐标 [i, j] 的最小值

int main()
{
    cin >> n;                                     //输入宽度

    memset(f, 0x3f, sizeof f);                    //注意边界条件

    for(int i = 1;i <= n;++ i)
        for(int j = 1, w;j <= n;++ j)
                                                  //枚举 i 和 j，注意顺序不能换
        {
            cin >> w;                             //这里是省空间，w 就是 w[i][j];
            if(i == 1 && j == 1) f[j] = w;        //注意当 i == 1 && j == 1 时，无法转移，所以要特判。

            else f[j] = min(f[j], f[j - 1]) + w;  //这里是优化，第 i 层只依赖于第 i 层和第 i - 1 层
                                                  //所以可以直接优化空间，这里的 f[j - 1] 对应的是 
                                                  //f[i][j - 1]，而 f[j] 对应的是 f[i - 1][j]
        }

    cout << f[n] << endl;                         //输出

    return 0;
}

请问路过的大佬，有没有“树套树套树”这种东西？（比如三个树状数组连环套（可能可以）解决三位偏序？）

如果有，能不能推荐一些习题qwq（最好是有c++题解可以学习的）

1015.摘花生

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

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

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

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

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

输入格式

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

接下来是 $T$ 组数据。

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

每组数据的接下来 $R$ 行数据，从北向南依次描述每行花生苗的情况

每行数据有 $C$ 个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目 $M$

输出格式

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

数据范围

$1 \le T \le 100$,
$1 \le R,C \le 100$,
$0 \le M \le 1000$

其实这道题我首先想的是记忆化搜索，但是发现更新顺序很像 DP，就用 DP 来切了

解法：DP 复杂度：O(n ^ 2)

状态表示

$f[i][j]$ 表示从左下角到位置 $[i, j]$ 的最大值

状态转移

很明显，枚举顺序是先行后纵

所以，$[i, j]$ （只能）依赖于 $[i - 1, j]$ 和 $[i, j - 1]$

也就是，f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w;

而第 i 层的答案只依赖于第 i 层和第 i - 1 层，容易想到滚动数组优化

在看到方程，发现不用滚动数组，直接用一维存即可（具体解释见代码）

一维转移：f[j] = max(f[j], f[j - 1]) + w;

答案表示

用二维存就是 f[n][m]

用一维存就是 f[m]

c++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100009;
int T, n, m;
int f[N];

void solve()
{
    cin >> n >> m;
    fill(f + 1, f + m + 1, 0);               //答案一定是非负整数，所以初始化所有 f[i] 为 0
    for(int i = 1;i <= n;++ i)               //枚举行
        for(int j = 1, w;j <= m;++ j)        //枚举列
        {
            cin >> w;                        //优化空间
            f[j] = max(f[j], f[j - 1]) + w;  //这里是优化，第 i 层只依赖于第 i 层和第 i - 1 层
                                             //所以可以直接优化空间，这里的 f[j - 1] 对应的是 f[i][j - 1]
                                             //而 f[j] 对应的是 f[i - 1][j]
        }

    cout << f[m] << endl;                    //f[m] 对应的是 f[n][m]
    return;
}

int main() 
{
    cin >> T;//多行数据
    while(T --) solve();
    return 0;
}

整理一下题解：

第一章 动态规划

数字三角形模型

1015.摘花生

1018. 最低通行费

最长上升子序列模型

1014.登山

背包模型

423.采药

状态机模型

1049.大盗阿福

区间DP

1068.环形石子合并

树形DP

1072.树的最长路径

单调队列优化DP

135.最大子序和

第二章 搜索

$Flood Fill$：

1097.池塘计数

第三章 图论

单源最短路的建图方式

1028.热浪

1029.信使

最小生成树

1140.最短网络

第四章 高级数据结构

第五章 数学知识

第六章 基础算法

前缀和

99.激光炸弹

RMQ

1273.天才的记忆

1014.登山

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有 $N$ 个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式

第一行包含整数 $N$，表示景点数量。

第二行包含 $N$ 个整数，表示每个景点的海拔。

输出格式

输出一个整数，表示最多能浏览的景点数。

数据范围

$2 \le N \le 1000$

根据题意，很明显用线性dp来解决

再观察上山下山的过程，上山就是上升子序列，下山就是下降子序列

所以考虑用最长上升（下降）子序列模型来解决

方案：线性dp 复杂度：$O(n ^ 2)$：

状态表示

$f[i]$ 表示以第 $i$ 个位置作为当前子序列的右端点的值

$g[i]$ 表示以第 $i$ 个位置作为当前子序列的右端点的值

状态属性

$f[i]$ 求最长上升子序列的最多景点个数

$g[i]$ 求最长下降子序列的最多景点个数

状态计算

$f[i] = max(f[i], f[j] + 1) (1 \le j < i \le n)$

$g[i] = max(g[i], g[j] + 1) (1 \le i < j \le n)$

$f$ 数组的求法和 $g$ 数组很像，因为把数组 $reverse$ 后，求新数组最长上升子序列就是求原数组最长下降子序列

答案表示

根据每一个点来划分：$ans = max$(包含 $i$ 的最长上升子序列 + 包含 $i$ 的最长下降子序列)

所以 $ans = max(f[i] + g[i] - 1)$

变量名解释：

$n$ 是景点数量

$x[]$：记录每个景点的海拔

$f[], g[]$：见上

$ans$ 答案，表示最多能浏览的景点数

c++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1009;

int n, x[N];                                  //景点数量和景点海拔
int f[N];                                     //求最长上升子序列
int g[N];                                     //求最长下降子序列
int ans = 0;

int main()
{
    cin >> n;

    for(int i = 1;i <= n;++ i)
                                              //首先求最长上升子序列
    {
        cin >> x[i]; f[i] = 1;                //注意子序列至少有一个节点
        for(int j = 1;j < i;++ j)             //枚举第二个节点
            if(x[i] > x[j])
                f[i] = max(f[i], f[j] + 1);
    }

    for(int i = n;i >= 1;-- i)
                                              //接着求最长下降子序列
    {
        g[i] = 1;                             //注意子序列至少有一个节点
        for(int j = n;j > i;-- j)
            if(x[i] > x[j])
                g[i] = max(g[i], g[j] + 1);   //求最长下降子序列
    }

    for(int i = 1;i <= n;++ i)
        ans = max(ans, f[i] + g[i] - 1);

    cout << ans << endl;

    return 0;
}

新版：

无敌版：

423.采药

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师

为此，他想拜附近最有威望的医师为师

医师为了判断他的资质，给他出了一个难题

医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

输入文件的第一行有两个整数 $T$ 和 $M$，用一个空格隔开

$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出文件包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

数据范围

$1 \le T \le 1000$,
$1 \le M \le 100$

输入样例：

70 3
71 100
69 1
1 2

输出样例：

3

一看这道看了几十遍的水题的名字，就知道是 01背包 （太经典了$QWQ$）

还是先写一下基本思路：

解法：01背包 复杂度：$O(nm)$：

01背包 的状态有：

状态表示：在前 i 个物品中，且使用体积不超过 j 的最大值

状态转移：$$f[i][j] =
\begin{cases}
f[i][j] = max { f[i − 1][j − v[i]] + w[i] } \text{选第 i 个物品} \
f[i][j] = f[i - 1][j] \text{不选第 i 个物品}
\end{cases}$$

因为状态 $f[i][j]$ 仅依赖于第 $i - 1$ 层的状态

所以可以在代码中优化掉一维空间（详见代码）

变量名解释

$m$ 代表总共能够用来采药的时间

$n$ 代表山洞里的草药的数目

$f[]$ 数组：dp方程

c++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1009;

int n, m;
//n 代表山洞里的草药的数目
//m 代表总共能够用来采药的时间

int f[N];//转移方程

int main()
{
    cin >> m >> n;//输入

    for (int i = 0, v, w;i < n;++ i)
    //枚举每一个物品 i
    {

        cin >> v >> w;
        //v 是采摘某株草药的时间
        //w  是这株草药的价值

        for (int j = m;j >= v;-- j)//枚举物品容量
            f[j] = max(f[j], f[j - v] + w);//转移方程
            //这里直接优化掉一维，枚举 j 的顺序
    }
    cout << f[m] << endl;//本来应该是 f[n][m]，这里优化掉了

    return 0;
}

135.最大子序和

输入一个长度为 $n$ 的整数序列，从中找出一段长度不超过 $m$ 的连续子序列，使得子序列中所有数的和最大

注意： 子序列的长度至少是 $1$。

输入格式

第一行输入两个整数 $n,m$。

第二行输入 $n$ 个数，代表长度为 $n$ 的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

$1 \le n,m \le 300000 $

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

首先，看到题目和数据范围：

求解子序列的题目很容易想到解法线性dp：

方法一：线性dp $O(n ^ 2)$：

线性dp 首先考虑状态等信息（和如何表示区间！通常用前缀和）

状态表示：$f[i]$ 表示以 $i$ 为右端点，长度不超过 $m$ 的子序列数字和最大值

状态计算：枚举区间右端点 $f[i] = max$ { $s[i] - s[j]$ } $(1 \le i - j \le m, i - m \le j \le i - 1)$

注：$s$ 数组是前缀和数组

很明显，直接计算会超时，于是考虑优化

方法二：线性dp + 单调队列优化 $O(n)$：

观察状态计算：

$s[i]$ 是一个常量，可以放在最后再加上

所以可以将方程转化为： $f[i] = s[i] - max$ { $s[j]$ }

求 $max$ { $s[j]$ } 就可以用单调队列维护s[j]的最小值

状态计算的复杂度就可以降为 $O(1)$

c++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 300009;

typedef long long ll;//十年OI一场空，不开long long见祖宗

int n, m;

int hh, tt;//对头和队尾

ll s[N];//前缀和数组

ll que[N];//单调队列

ll ans = -1e18;//答案

int main()
{
    cin >> n >> m;

    for (int i = 1, x;i <= n;++ i) cin >> x, s[i] = s[i - 1] + x;//输入原数组，更新前缀和数组

    for(int i = 1;i <= n;++ i)
    //枚举右端点
    {
        while(hh <= tt && i - que[hh] > m) hh ++;//更新队头

        ans = max(ans, s[i] - s[que[hh]]);//更新答案，注意不要忘记加上s[i]

        while(hh <= tt && s[que[tt]] >= s[i]) tt --;//更新队尾

        que[++ tt] = i;//添加新的节点
    }

    cout << ans << endl;//输出答案

    return 0;
}

99.激光炸弹

地图上有 $N$ 个目标，用整数 $X_{i}, Y_{i}$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 $R \times R$ 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 $x，y$ 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 $N$ 和 $R$，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来 $N$ 行，每行输入一组数据，每组数据包括三个整数 $X_{i}, Y_{i}, W_{i}$，分别代表目标的 $x$ 坐标，$y$ 坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

$0 \le R \le 10^9$
$0 < N \le 10000$,
$0 \le X_{i}, Y_{i} \le 5000$
$0 \le W_i \le 1000$

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

二维前缀和模板题：

注意 r 的范围和平面区间的计算

$mp[][]$ 数组：二维前缀和，用来 $O(1)$ 时间计算平面数字和

$mp[i][j] - mp[i - r][j] - mp[i][j - r] + mp[i - r][j - r]$

$ans$：最终总价值数目

$n$：目标个数，$r$：正方形的边长

c++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5009;

int mp[N][N];//二位前缀和数组
int n, r, ans = 0;

int main()
{
    cin >> n >> r;

    r = min(r, 5001);

    for(int i = 1, x, y, w;i <= n;++ i)
    {
        cin >> x >> y >> w;
        mp[x + 1][y + 1] += w;//此时 mp 数组的含义就是初始地图
    }
    for(int i = 1;i <= 5001;++ i)//坐标最多 5000
        for(int j = 1;j <= 5001;++ j)//按顺序枚举坐标
            mp[i][j] = mp[i - 1][j] + mp[i][j - 1] - mp[i - 1][j - 1] + mp[i][j];
            //注意顺序

    for(int i = r;i <= 5001;++ i)
        for(int j = r;j <= 5001;++ j)//状态计算
            ans = max(ans, mp[i][j] - mp[i - r][j] - mp[i][j - r] + mp[i - r][j - r]);

    cout << ans << endl;
    return 0;
}

1097.池塘计数

农夫约翰有一片 $N*M$ 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $N$ 行，每行包含 $M$ 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出格式

输出一个整数，表示池塘数目。

数据范围

$1 \le N,M \le 1000$

输入样例：

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出样例：

3

这道题就是 Flood Fill 的模板题，直接上变量解释：

$dx[]$ 数组：方向数组，用来存八连通方向的横轴变化

$dy[]$ 数组：方向数组，用来存八连通方向的纵轴变化

$mp[][]$ 数组：初始数组，用来存输入的地图

$ans$：用来存连通块个数

$n$：行数，$m$：列数

注意每一次 $dfs$ 时，都要将当前节点换成土地

c++ 代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1009;

int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};//方向
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};//方向

int n, m, ans = 0;
char mp[N][N];

void dfs(int x, int y)
{
    mp[x][y] = '.';//更新当前节点的类型
    for(int i = 0;i < 8;++ i)//枚举八连通方向
        if(mp[x + dx[i]][y + dy[i]] == 'W')//如果是水
            dfs(x + dx[i],y + dy[i]);//dfs 下一个节点
}

int main()
{
    cin >> n >> m;//输入
    for(int i = 1;i <= n;++ i)
        for(int j = 1;j <= m;++ j)
            cin >> mp[i][j];//输入

    for(int i = 1;i <= n;++ i)
        for(int j = 1;j <= m;++ j)
            if(mp[i][j] == 'W')
                dfs(i, j), ans ++;//每递归一个连通块，ans ++
    cout << ans << endl;
    return 0;
}