30个题型+代码(冲刺2023蓝桥杯)(下)

如果你想冲省一拿22年A组为例你得拿60分也就是2道填空题 + 4道编程题

5 + 5 + 10 + 10 + 15 + 15

省赛需要掌握的有

前缀和差分二分双指针递归递推BFSDFSDijkstra, Floyd质数筛最大公约数背包dp线性dp区间dp组合计数快速幂哈希并查集博弈论

围绕省赛需要掌握的类型针对性地下手

先给大家看个时间复杂度来源于AcWing

二十一筛质数

二十二最大公约数

二十三快速幂

二十四组合计数

二十五博弈论

二十七线性DP

新娘阿花 - 金玟岐 - 单曲 - 网易云音乐

单车恋人 - 后弦 - 单曲 - 网易云音乐

知识分析

动态规划其实就是通过记住求过的解来节省时间通过避免重复计算已经算过的东西

通常用一维 / 二维 / 三维数组保存求过的解这里的解是通过决策保存有可能达到最优的局部解 ------关于开几维数组看你需要几个变量

1线性dp就是普通dp / 裸dp实际上就是递推 + 一个数组(保存过程中需要的数据)

2动态规划与分治的区别

1动态规划子问题重叠分治子问题相互独立

比如斐波那契数列更适合用dp来做因为F(7) = F(6) + F(5),

而F(6) = F(5) + F(4)容易发现F(5)在分治里被计算了2次

而dp用一维数组dp[i]将F(i)保存起来后续需要子问题的解直接从数组找就行

-----2同时如果子问题的最优解能代表整个问题的最优解才适用于动态规划

dp解斐波那契数列

#include<iostream>
using namespace std;
int dp[40];
int fibo(int n)
{
    if(n <= 1) return n;
    for(int i = 2; i <= n; ++i)
        dp[i] = dp[i - 2] + dp[i - 1];
    return dp[n];
}
int main()
{
    dp[0] = 0, dp[1] = 1;
    int n;
    cin>>n;
    cout<<fibo(n);
    return 0;
}

分治解斐波那契数列

#include<iostream>
using namespace std;
int fibo(int n)
{
    if(n <= 1) return n;
    return fibo(n - 1) + fibo(n - 2);
}
int main()
{
    int n;
    cin>>n;
    cout<<fibo(n);
    return 0;
}

显而易见分治比dp少了个一维数组保存中间的结果但是慢了上百倍具体参考这几个博客

然而当我做了2题后发现动规不一定要数组保存中间结果它也可以是通过递推/递归/分治等来实现只要能避免子问题的重复计算提高速度就行

→ (20条消息) 分治法与动态规划求解斐波那契数列_kingdragonfly的博客-CSDN博客

→ (20条消息) 动态规划与分治法异同_动态规划和分治法的区别_白给、少年的博客-CSDN博客

→ 动态规划和分治法的区别 - Frank_Allen - 博客园 (cnblogs.com)

我在学习dp过程看的其他博客强烈建议全看一遍不做题最多2小时就吸收完了

DP核心

→ (9条消息) 算法-动态规划 Dynamic Programming--从菜鸟到老鸟_HankingHu的博客-CSDN博客

→ (9条消息) 经典中的经典算法:动态规划(详细解释,从入门到实践,逐步讲解)_动态规划算法_god 's favored one的博客-CSDN博客

→ C/C++ 动态规划算法 (ppmy.cn)

→ (12条消息) C++之动态规划动态规划入门_DJS编程小白的博客-CSDN博客

→ (10条消息) C++动态规划详解_Godvvvvvvv的博客-CSDN博客

→ (9条消息) 告别动态规划连刷40道动规算法题我总结了动规的套路_Hollis Chuang的博客-CSDN博客

看完这9个博客请再来看3个视频

视频中的思路都差不多先摆出方法论dp的步骤再结合方法论套路/模板套到每一道题目上

dp的步骤

一确定 dp[i] 或者 dp[i][j] 中 dp[i] 和 i dp[i][j] 和 i , j 的具体含义状态比如斐波那契数列中dp[i] 表示第 i 个斐波那契数i 表示第几个

二找递推公式通过最后一步将问题转化成子问题

三如何初始化你要初始化多少个初始化的值是什么同时避免越界

四确定遍历顺序一维前往后后往前二维从左上角右下角甚至是中间等开始遍历

五打印dp数组cout或者printf的形式debug

B站10万浏览量以上的up讲的都差不多关于dp就4个步骤就是以上的步骤

dp的题型

一计数

·走到右下角的方式有多少种

·选出k个数和为sum的可能数

·青蛙每次跳n格跳到最后一格的方案数

二求最大最小值

·左上角 -> 右下角路径的最大数字和

·最长上升子序列长度

三求存在性

·取石子先手是否必胜

·能不能选出k个数使得和为sum

·青蛙能否跳到最后一个格子

观察上述dp题型求的都是种类数个数数字的和长度true/false都是一个结果而非路径

如果要输出路径不用dp只能输出结果而已一般用dfs或bfs

从此再也不怕动态规划了动态规划解题方法论大曝光 | 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩_bilibili

手把手带你入门动态规划 | 对应力扣题号509.斐波那契数_哔哩哔哩_bilibili

2小时超详细推理过程建议看看

【动态规划专题班】ACM总冠军、清华+斯坦福大神带你入门动态规划算法_哔哩哔哩_bilibili

然后可以开始做题了循序渐进由简到繁

一1112: 平面分割

标签基础题动态规划

思路

1确定状态含义

这里我们用dp[i]表示前 i 条直线分割的最大区域数i 表示用到了 i 条直线

怎么分割才是最大区域数呢新的直线和所有旧的直线都相交就行也就是不平行

2找递推公式

由上图dp[p] = 2 * p是显然的后续增加第 i 条直接就增加 i 个区域

dp[i] = dp[i - 1] + i;

3初始状态当然就是dp[p] = 2 * p;

4遍历顺序从前到后

AC 代码1

#include<iostream>
using namespace std;
int dp[510], n, p;
int main()
{
    cin>>n>>p;
    dp[p] = 2 * p;
    for(int i = p + 1; i <= n; ++i)
        dp[i] = dp[i - 1] + i;
    cout<<dp[n];
    return 0;
}

AC 代码2

用int型变量代替了dp[]

#include<iostream>
using namespace std;
int sum, n, p;
int main()
{
    cin>>n>>p;
    sum = 2 * p;
    for(int i = p + 1; i <= n; ++i)
        sum += i;
    cout<<sum;
    return 0;
}

二1701: [NewOJ Contest 1] 01卡片

P1701 - [NewOJ Contest 1] 01卡片 - New Online Judge (ecustacm.cn)

标签基础题模拟动态规划

AC 暴力 O(nlogn)

本地编译器代码

#include<iostream>
using namespace std;
long long sum0, sum1;
//10转2后含有的0和1
void binary(int x)
{
    while(x) {
        if(x % 2 == 0)
            sum0 += 1;
        else if(x % 2 == 1)
            sum1 += 1;
        x /= 2;
    }
}
int main()
{
    for(int i = 1; i <= 20222022; ++i)
        binary(i);
    cout<<sum0<<" "<<sum1;
    return 0;
}

测试了2组数据修改 i <= 5和 i <= 10的输出都正确了可以提交

提交代码

#include<iostream>
using namespace std;

int main()
{
    cout<<230401142<<" "<<241595002;
    return 0;
}

AC 递推 O(n)

将佬的思路加进来主要为了加深对动规的理解要我写也写不出来

不过我写成了递推

fzl的思路很清奇反正像我一样的大多数普通人估计是想不到除非经过大量训练

思路来源博客B题 (96条消息) NewOJ 2022 Contest 1题解_傅志凌的博客-CSDN博客

首先

dp[i]表示前i个数二进制表示中0的个数和记s[i]表示i的二进制中0的个数

dp[6] = (s[1] + s[3] + s[5]) + (s[2] + s[4] + s[6])

s[1] + s[3] + s[5] = s[0] + s[1] + s[2] = dp[2]

s[2] + s[4] + s[6] = 3 + s[1] + s[2] + s[3]

即dp[6] = 3 + dp[2] + dp[3]

由此扩展到所有偶数

dp[n] = n / 2 + dp[n / 2] + dp[n / 2 - 1]

类似对于奇数

dp[n] = n / 2 + 2 * dp[n / 2] --------以上除法均向下取整

类似对于1的个数。。。。

然而我写出来的看似想用动规实际上只是递推

如果判断子问题重复计算呢自己模拟下递归树看看是否一直有重复就行

从2遍历到20222022显然中间很多步骤并不需要

#include<iostream>
using namespace std;
int dp0[20222032], dp1[20222032];
int main()
{
    //初始化dp数组
    dp0[1] = 0, dp1[1] = 1;
    //递推
    for(int i = 2; i <= 20222022; ++i) {
        if(i % 2 == 0) { //偶数
            dp0[i] = dp0[i / 2] + dp0[i / 2 - 1] + i / 2;
            dp1[i] = dp1[i / 2] + dp1[i / 2 - 1] + i / 2;
        }
        else { //奇数
            dp0[i] = 2 * dp0[i / 2] + i / 2;
            dp1[i] = 2 * dp1[i / 2] + i / 2 + 1;
        }
    }
    cout<<dp0[20222022]<<" "<<dp1[20222022];
    return 0;
}

AC 动规 O(logn)

这个是fzl的原代码

动规的思路递推来实现容易发现这个思路没有重复计算比如20222022直接到了10111011

中间计算的每一步都是需要的不像前面的暴力或者遍历+递推重复计算了大量子问题

#include<bits/stdc++.h>
using namespace std;
int Zero(int x)
{
    if(x <= 1)return 0;
    if(x & 1) return 2 * Zero(x / 2) + x / 2;
    else return Zero(x / 2) + Zero(x / 2 - 1) + x / 2;
}
int One(int x)
{
    if(x <= 1)return x;
    if(x & 1) return 2 * One(x / 2) + x / 2 + 1;
    else return One(x / 2) + One(x / 2 - 1) + x / 2;
}
int main()
{
    cout<<Zero(20222022)<<" "<<One(20222022)<<endl;
    return 0;
}

三1114: 放苹果

P1114 - 放苹果 - New Online Judge (ecustacm.cn)

标签基础题动态规划递归

AC很容易找找题解模仿着一写就以为自己会了

难得是把这题摸透一点比如

为什么自己的代码时间复杂度那么高(O(2^n, n^3, n^2))而别人的那么低(O(logn, n, nlogn))

如果数据量达到1e41e5你还能AC吗如果题目换个条件你还会做吗

如何改进每一行代码该怎么解释过一周再遇到一道类似的你能在半小时内AC吗

思路

dp[i][j]表示将 i 个苹果放入 j 个盘子状态

dp[i][j] = dp[i][j - 1] + dp[i - j][j]递推式

dp[i][1] = 1, dp[0][j] = 1;初始化

前往后遍历遍历方式

分析

首先注意题目字眼

1“同样的苹果盘子” --> 5, 1, 1和1, 5, 1一样所以不能用dfs搜索

2“允许有空的盘子” --> 这句话影响了递推式怎么写

主要解释下递推式和初始化

假设此时有 i 个苹果j 个盘子i 个苹果放入 j 个盘子的方案数可以分成两部分思考

等于将 i 个苹果放入 j - 1 个盘子加上先在 j 个盘子每个盘子放一个苹果再将剩下

i - j个苹果放入 j 个盘子的方案数写出来就是dp[i][j - 1] + dp[i - j][j]

---------------------------------------------------------

再解释下初始化

初始化是由递推式推导过来的先写出递推式才能进一步找到初始条件

解释将任何数量的苹果放入一个垃圾桶中或没有垃圾桶可放苹果时的方案数都为 1

由于递推式中 j 的变化只有 j - 1的情况显然当 j == 1只剩一个盘子时所有的苹果只能放进这一个盘子是一种情况所以dp[i][1] = 1

第二个就是i 的变化只有 i - ji - j == 0的情况显然存在此时剩0个苹果所以也只有一种可能假设此时 i = 1, j = 100第一步就是变成 i = 1, j = 1下一步直接就 i = i - j直接=0了所以是1种

初始化的状态表示递归的终点

对比

本题中第二个代码使用了动规的思路将子问题的解保存到二维数组中通过递推得到当前问题的解避免了重复计也减小了问题的规模

而第一个代码虽然简单易懂但复杂度指数级别数据量大就会TLE

AC 递推 O(2^n)

这个是指数级复杂度与dp只有一个记忆化的距离其实dp和记忆化是一个东西说到底是一种思想

复杂度高达2^n因为每个苹果都有2种选择进 / 不进盘子

#include<iostream>
using namespace std;
int m, n;
//x个苹果放入y个垃圾桶
int dfs(int x, int y)
{
    if(x < y)
        return dfs(x, x); //去掉多于垃圾桶无影响
   if(x == 0 || y == 1) //0个苹果或1个垃圾桶, 有递推式判断初始状态
        return 1;
   return dfs(x, y - 1) + dfs(x - y, y);
}
int main()
{
    int t;
    cin>>t;
    while(t--) {
        cin>>m>>n;
        cout<<dfs(m, n)<<endl;
    }
    return 0;
}

AC 动规 O(mn)

这个可能数据量到10^4甚至10^5都不会超时

#include<iostream>
using namespace std;
int dp[30][30], m, n, t;
int main()
{
    cin>>t;
    while(t--) {
        cin>>m>>n;
        //初始状态, 尽量从0开始初始化
        for(int i = 0; i <= m; ++i) dp[i][1] = 1; //剩1种可能
        for(int j = 0; j <= n; ++j) dp[0][j] = 1; //同上
        //递推式
        for(int i = 0; i <= m; ++i) //i个苹果放入j个垃圾桶
            for(int j = 1; j <= n; ++j) {
                if(i < j) dp[i][j] = dp[i][i]; //去掉多余盘子
                else dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                //else不要漏
            }
        cout<<dp[m][n]<<endl;
    }
    return 0;
}

四P1115 最大子段和

P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签动态规划分治递推线性数据结构普及-

你可以认为这题是第五题的铺垫实际上我先做了第五题才回来写这题

本题采用3种解法1双指针 2前缀和 3动态规划

知识点

双指针的认识还很浅缺乏练习真遇到大概率做不出来

→ 双指针 - OI Wiki (oi-wiki.org)

→ 前缀和 & 差分 - OI Wiki (oi-wiki.org)

AC 双指针

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int a[200010], ans = -1e9, sum;
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%lld", &a[i]);
    //ans保存最大子段和, sum保存当前子段和
    //i是右边界, sum代替了左边界的作用
    for(int i = 0; i < n; ++i) {
        if(sum < 0) sum = a[i]; //这里是= a[i]而不是0, 存在负数
        else sum += a[i];
        ans = max(ans, sum);
    }
    cout<<ans;
    return 0;
}

AC 前缀和

注意

1前缀和可以在输入时求出

2显而易见ans初始值设置要小于-1e4关键是int Min = 0;这个不能设置为尽可能小的负数

否则无法取到第1至第i个元素的最小前缀和第1个会取不到

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int a[200010], s[200010], ans = -1e9; //s[]前缀和
int main()
{
    int n;
    scanf("%d", &n);
    //读入的同时得到前缀和
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    int Min = 0; //Min是前缀和在[0, i]的最小值
    //边取子段和边得到当前最小前缀和
    for(int i = 1; i <= n; ++i) {
        ans = max(ans, s[i] - Min);
        Min = min(Min, s[i]);
    }
    cout<<ans;
    return 0;
}

动规思路

1状态

dp[i]表示以a[i]结尾的最大子段和

2递推式也称状态转移

dp[i] = max(dp[i - 1] + a[i], a[i]);

3初始

dp[0] = 0假设a[i]从1开始输入

4遍历

从前往后

AC 动规

#include<iostream>
using namespace std;
int dp[200010], a[200010], ans = -1e9;
int main()
{
    int n;
    cin>>n;
    for(int i = 1; i <= n; ++i)
        cin>>a[i];
    dp[0] = 0;
    //dp[i]表示a[i]结尾的最大子段和
    for(int i = 1; i <= n; ++i)
        dp[i] = max(dp[i - 1] + a[i], a[i]);
    //遍历找出1~n最大子段和
    for(int i = 1; i <= n; ++i)
        ans = max(ans, dp[i]);
    cout<<ans;
    return 0;
}

五1051. 最大的和

1051. 最大的和 - AcWing题库

标签DP线性DP简单前后缀分解

AC 50% O(n^2)暴力

Max函数每遍历一次就是n主函数中再遍历一次分界点也是n所以复杂度O(n^2)对于30*5e4*5e4已经达到了7.5 * 10^10 >> 10^8所以Time Limit

注意考虑到结果可能小于0因为两个子段必然是存在的如果全为负数...

所以代码第8和30行都应初始化为-1e9(虽说-1e4也都AC了但是往大了初始化安全)

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int a[50010], t, n, ans;
int Max(int x)
{
    int sum1 = 0, sum2 = 0, ans1 = -1e9, ans2 = -1e9;
    //判断前半段
    for(int i = 0; i <= x; ++i) {
        if(sum1 < 0)
            sum1 = 0;
        sum1 += a[i];
        ans1 = max(ans1, sum1);
    }
    //判断后半段
    for(int i = x + 1; i < n; ++i) {
        if(sum2 < 0)
            sum2 = 0;
        sum2 += a[i];
        ans2 = max(ans2, sum2);
    }
    return ans1 + ans2; //返回最大两字段和
}
int main()
{
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        ans = -1e9;
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        //分界点i,
        for(int i = 0; i < n - 1; ++i)
            ans = max(ans, Max(i));
        cout<<ans<<endl;
    }
    return 0;
}

AC 动规 O(n)

看完y总的思路发现其实对一段的处理和前面的暴力差不多

然而有2段方法是预处理下前缀最大和后缀最大和第一次接触这种方法

解析在注释里

思路

1先确定状态也就是注释中的

dp[i]是a[i]结尾的最大子段和
g[i]是a[0]到a[i]最大子段和
h[i]是a[i]到a[n - 1]最大子段和

2找递推式

说下预处理前缀的dp[i] = max(dp[i - 1] + a[i], a[i])注意最后是a[i]而不是0

3初始状态

我们根据递推式推初始

预处理前缀

初始i == 1i - 1 == 0g[0]表示a[0]到a[0]的最大子段和就是a[0]dp[0]表示a[0]到a[0]的最大子段和也是a[0]所以dp[0] = a[0], g[0] = a[0]

预处理后缀

当i = n - 1i + 1 == n由于输入a[]从0开始的考虑到存在负数为了保证取到想要的max值我们需要将dp[n]和h[n]都设为-1e9-1e4就能过

4遍历顺序在初始状态中说完了

AC 代码

其实第21行初始化为-1e4即可因为单个数最小才-10000

只是最后的ans初始化需要-1e9-50000*10000 = -5e8

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int a[50010], g[50010], h[50010]; //输入数组,前缀数组,后缀数组
int dp[50010], t, n;
//dp[i]是a[i]结尾的最大子段和
int main()
{
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        //预处理前缀, g[i]是a[0]到a[i]最大子段和
        dp[0] = a[0], g[0] = a[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = max(dp[i - 1] + a[i], a[i]);
            g[i] = max(dp[i], g[i - 1]);
        }
        //预处理后缀, h[i]是a[i]到a[n - 1]最大子段和
        dp[n] = -1e9, h[n] = -1e9;
        for(int i = n - 1; i >= 0; --i) {
            dp[i] = max(dp[i + 1] + a[i], a[i]);
            h[i] = max(dp[i], h[i + 1]);
        }
        //分界点i
        int ans = -1e9;
        for(int i = 0; i < n; ++i) {
            ans = max(g[i] + h[i + 1], ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

空间优化

补充个用变量sum代替dp数组对空间进行优化的代码只进行了细微的修改

为什么能去掉dp[]呢看看上面代码第17和23行dp[i]只和它的上一个相关

比如假设一个

dp[i] = dp[i - 1] + a[i];
//或者
dp[i] = dp[i + 1] + a[i];

显然可以表示成当然这里看遍历顺序sum分别代表dp里的-1和+1都是上一个的意思

sum = sum + a[i];
//或者
sum = sum + a[i];

AC 代码2

只需要把所有dp出现的地方全换成sum就行了

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int a[50010], g[50010], h[50010]; //输入数组,前缀数组,后缀数组
int t, n, sum;
//dp[i]是a[i]结尾的最大子段和
int main()
{
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        //预处理前缀, g[i]是a[0]到a[i]最大子段和
        sum = a[0], g[0] = a[0];
        for(int i = 1; i < n; ++i) {
            sum = max(sum + a[i], a[i]);
            g[i] = max(sum, g[i - 1]);
        }
        //预处理后缀, h[i]是a[i]到a[n - 1]最大子段和
        sum = -1e9, h[n] = -1e9;
        for(int i = n - 1; i >= 0; --i) {
            sum = max(sum + a[i], a[i]);
            h[i] = max(sum, h[i + 1]);
        }
        //分界点i
        int ans = -1e9;
        for(int i = 0; i < n; ++i) {
            ans = max(g[i] + h[i + 1], ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

对比下空间当然空间优化只在面试考算法比赛只看时间复杂度

----------->>>>

六895. 最长上升子序列

895. 最长上升子序列 - AcWing题库

标签动态规划线性DP最长上升子序列简单

注意它没说连续做动规的题一定要抠字眼每个字眼都会对递推式产生影响甚至有些字眼导致无法用dp解决问题

1明确状态

错误思路dp[i]表示前 i 个元素中递增子序列不一定连续的最大长度

这样你很难写的出递推式

正确思路dp[i]表示以第 i 个元素结尾的递增子序列的最大长度

递推式dp[i] = max(dp[j] + 1, dp[i])

其中 i 是外层循环的j 是内层循环内层循环从第 0 个元素遍历到第 i - 1 个元素

如果a[j] < a[i]说明可以dp[j] + 1最后dp[i]取到前面dp[j]的最大值 + 1

2初始化

显而易见一个元素时子序列的长度都为1所以将dp[i]全初始化为1

这样最后求结果只需要遍历一遍dp数组找到最大值

这一步可以放在前面的二层循环里

----------------------------------------------------------

思路参考这个博客(7条消息) 最长上升子序列动态规划_syc_36的博客-CSDN博客

其实还有一种贪心 + 二分O(nlogn)的方法...感兴趣的自己试试

3代码

即使 n <= 1e4 还是可以做的如果到了 n <= 1e5只能贪心 + 二分了

额外的测试

8
8 7 2 1 2 5 1 7
4

有个坑ans记得初始化为1ans = 0的话当输入这个会输出0因为避开了两层for循环

1
1
0

AC DP O(n^2)

#include<iostream>
using namespace std;
int dp[1010], a[1010], ans = 1, n;
int main()
{
    cin>>n;
    for(int i = 0; i < n; ++i) {
        cin>>a[i]; //读入序列
        dp[i] = 1; //初始化dp数组
    }
    for(int i = 1; i < n; ++i)
        for(int j = 0; j < i; ++j) {
            if(a[i] > a[j]) {
                dp[i] = max(dp[j] + 1, dp[i]);
                ans = max(ans, dp[i]);
            }
        }
    cout<<ans;
    return 0;
}

二十六背包DP

Edamame (ft. Rich Brian) - bbno$/Rich Brian - 单曲 - 网易云音乐

不打竞赛只是准备大厂面试的话搞清楚01背包和完全背包就够了

因为力扣据说只有01背包和完全背包的题

01背包更是基础中的基础完全和多重背包都是在01的基础上进化来的

先区分下01完全多重背包

01背包n种物品每种物品只有1个即每个物品只能选0次或1次

完全背包n种物品每种物品无限个

多重背包n种物品每种物品的个数各不相同

01背包知识

视频

这2个视频01背包讲的很清楚

带你学透0-1背包问题| 关于背包问题你不清楚的地方这里都讲了| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

带你学透01背包问题滚动数组篇 | 从此对背包问题不再迷茫_哔哩哔哩_bilibili

下面这个视频补充理解

→ 动态规划DP0-1背包_哔哩哔哩_bilibili

博客

→ 背包 DP - OI Wiki (oi-wiki.org)

思路

1状态确定

dp[i][j]表示只能放前 i 个物品的前提下容量为 j 的背包的最大总价值

或者说假设下标从0开始表示下标为[0, i]之间的物品任取放进容量为 j 的背包...

如果从1开始就是下标为[1, i]之间的物品...

2递推式

分两步讨论

1不放物品 i dp[i][j] = dp[i - 1][j]表示剩余容量不变从只能放前 i 个物品 -->

只能放前 i - 1个物品

2放物品 i dp[i][j] = dp[i - 1][j - weight[i]] + value[i]

所以在两者中取最大值dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

(后面熟悉后weight[i] --> w[i]value[i] --> v[i])

3初始化

凑合着看把

显然对于二维我们只需初始化第一列和第一行第一列初始化为0第一行从背包容量大于等于weight[0]开始要初始化为value[0]

如何得出上述初始化的呢

当然是根据递推式以及画图来推的递推式dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

i - 1表示正上方加上个j - w[i]就是左上方所以当前的dp[][]来自上一行的两个方向为保证后续dp[][]能实现只需初始化第一列和第一行

再说下二维 --> 一维也就是滚动数组

二维正 / 逆序遍历都可以而且先遍历物品( i )还是背包( j )都行

但是一维只能逆序遍历

解释二维数组利用的是左上方和正上方的数据不存在覆盖所以正向 / 反向遍历都可以

但是转变为一维数组后正向遍历会覆盖左边数据所以得反着来可以去第2个视频看看

倒叙遍历保证一维dp[]中每个物品最多被添加一次

滚动数组递推式dp[j] = max(dp[j], dp[j - w[i]] + v[i])把 i 部分去掉就行

完全背包知识

-----------------------------分界线------------------------------

一2. 01背包问题

2. 01背包问题 - AcWing题库

标签背包DP模板简单

01背包模板题

我先用二维dp[][]试试会不会MLE(Memory Limit Exceeded)

再用一维dp[]做

第一次敲完样例对了又测试了一组加上打表表不对虽说答案是对的一看初始化错了

补充打表属于dp的第4步对比自己草稿纸上的过程是debug的好方法

初始化代码和输入输出

//初始化
for(int j = 0; j < m; ++j)
    if(j >= w[0])
        dp[0][j] = v[j];
//输入输出
4 5
3 2
4 2
2 4
1 3
0  0  0  3  0  0
0  0  0  3  2  2
0  0  4  4  4  7
0  3  4  7  7  7
7

当然有些人把初始化这步省掉了他们是直接背模板不去探究细节

或者说对细节熟悉到一定程度了我初学所以会探究下细节

j < m; --> j <= m

dp[0][j] = v[j] --> dp[0][j] = v[0];

也就是将第一行背包容量可以满足物品0体积的部分初始化为物品0的价值

最后输出也要修改cout<<dp[n - 1][m - 1] --> cout<<dp[n - 1][m];

提交第一次就AC了这是属于自己debug的过程更契合蓝桥杯OI赛制

以为过了样例和额外的测试就不是0分了你得打表看看过程

AC 代码

#include<iostream>
using namespace std;
int dp[1010][1010], w[1010], v[1010], n, m;
int main()
{
    cin>>n>>m; //n件物品, 最大容量m
    //读入每件物品重量, 价值
    for(int i = 0; i < n; ++i)
        cin>>w[i]>>v[i];
    //初始化
    for(int j = 0; j <= m; ++j)
        if(j >= w[0])
            dp[0][j] = v[0];
    //dp核心代码
    for(int i = 1; i < n; ++i)
        for(int j = 1; j <= m; ++j) {
            if(j < w[i]) //装不下
                dp[i][j] = dp[i - 1][j];
            else //能装下再选择, 装 / 不装
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        }
    cout<<dp[n - 1][m];
    return 0;
}

二十八区间DP

二十九树型DP

三十树状数组

总结

大一参加蓝桥杯注定无法取得好成绩因为数据结构是大二上才学先不谈数据结构单就算法来说大一能掌握一半的基础算法都不错了只是一半的基础算法最多也就C++A组省二

1对拍找bug很棒的方法

2s.find(), s.substr()

#include<cstring> //s.substr(), s.find()

string s1 = s.substr(j, i); //下标j开始, 截取i个字符
if(s.find(s1, j + 1) == string::npos)
//没有找到子串, 返回string::npos

if(s.find(s1, j + 1) != string::npos)
//找到子串

3map的迭代器

#include<iostream>
#include<map>
using namespace std;
map<int, int>m;
for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it) //迭代器
    printf("%d ", it->second);

4蓝桥杯技巧