头像

陌上花开Charlie

$\href{https://www.acwing.com/blog/content/22179/}{{个人主页}}$ 六年级蒟蒻 封禁家族




在线 


最近来访(343)
用户头像
种花家的兔兔
用户头像
dp菜苟
用户头像
AcWing2AK
用户头像
云衣醉梦
用户头像
Java不是瓜哇
用户头像
wangyc
用户头像
江南诗诗
用户头像
光无影
用户头像
Finn2009
用户头像
incra
用户头像
Lucas〆
用户头像
南岸以南南岸哀
用户头像
lgvc
用户头像
OI
用户头像
hyz123
用户头像
南栀向暖
用户头像
Changwoo
用户头像
JcWing
用户头像
Resurgence1001
用户头像
丰起水


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;
}


分享 yeah~

新版:

黑羽快斗.png

无敌版:

yeah




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;
}