精华内容
下载资源
问答
  • acwing算法提高课
    2022-05-26 21:00:12


    前言

    本文为记录复习acwing算法提高课所用。
    提示:最好观看完视频阅读。不推荐直接。

    Acwing.12 背包问题具体方案

    题目描述

    有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
    第 i件物品的体积是 vi,价值是 wi。
    求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
    
    输出 字典序最小的方案。这里的字典序是指:
    所选物品的编号所构成的序列。物品的编号范围是 1…N。
    
    输入:
    第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
    接下来有 N行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
    输出 : 最小字典序,每个序号空格分开。
    
    

    思路

    在求解最大值时选用二维数组表示时记录了第 i 个物品是否选择,倒推 如果选中了该物体 i 那么必有f[i][j] == f[i-1][j- v[i]] + w[i];
    为了满足最小字典序那么选择物品的顺序就从 后往前遍历,最后从 1 往后遍历。 如果选择了就输出。

    代码

    #include <iostream>
    using namespace std;
    const int N = 1010 ;
    int f[N][N];
    int w[N],v[N];
    int n,m;
    int main()
    {
        cin>>n>>m;
        for(int i = 1 ;i <= n ; ++i )
        cin>>v[i]>>w[i];
        for(int i = n ; i > 0 ; -- i )
            for(int j = 0; j <= m ;++j)
            {
             f[i][j] = f[i + 1][j];
                if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
            }
            int j = m;
            for(int i = 1 ; i <= n ; ++i)
                {
                if( j >= v[i]   && f[i][j]  ==  f [i+1][j - v [i]]+w[i]) 
                {
                 cout<<i<<" ";
                 j-=v[i];
                }
                 }
             return 0;
    }
    
    更多相关内容
  • acwing算法基础讲义

    2022-04-30 10:36:44
    acwing算法基础讲义
  • 文章目录第一章 动态规划 (完成情况:64/68)数字三角形模型最长上升...图论 (完成情况:55/58)单源最短路的建图方式单源最短路的综合应用单源最短路的扩展应用Floyd算法最小生成树最小生成树的扩展应用负环差分约束最近

    第一章 动态规划 (完成情况:64/68)

    包括数字三角形模型、最长上升子序列模型、背包模型、状态机、状态压缩DP、区间DP、树形DP、数位DP、单调队列优化DP、斜率优化DP等内容

    数字三角形模型

    AcWing 1015. 摘花生
    AcWing 1018. 最低通行费
    AcWing 1027. 方格取数
    AcWing 275. 传纸条

    最长上升子序列模型

    AcWing 1017. 怪盗基德的滑翔翼
    AcWing 1014. 登山
    AcWing 482. 合唱队形
    AcWing 1012. 友好城市
    AcWing 1016. 最大上升子序列和
    AcWing 1010. 拦截导弹
    AcWing 187. 导弹防御系统
    AcWing 272. 最长公共上升子序列

    背包模型

    AcWing 423. 采药
    AcWing 1024. 装箱问题
    AcWing 1022. 宠物小精灵之收服
    AcWing 278. 数字组合
    AcWing 1023. 买书
    AcWing 1021. 货币系统
    AcWing 532. 货币系统
    AcWing 6. 多重背包问题 III
    AcWing 1019. 庆功会
    AcWing 7. 混合背包问题
    AcWing 8. 二维费用的背包问题
    AcWing 1020. 潜水员
    AcWing 1013. 机器分配
    AcWing 426. 开心的金明
    AcWing 10. 有依赖的背包问题
    AcWing 11. 背包问题求方案数
    AcWing 12. 背包问题求具体方案
    AcWing 734. 能量石
    AcWing 487. 金明的预算方案

    状态机模型

    AcWing 1049. 大盗阿福
    AcWing 1057. 股票买卖 IV
    AcWing 1058. 股票买卖 V
    AcWing 1052. 设计密码
    AcWing 1053. 修复DNA(此题未完成)

    状态压缩DP

    AcWing 1064. 小国王
    AcWing 327. 玉米田
    AcWing 292. 炮兵阵地
    AcWing 524. 愤怒的小鸟
    AcWing 529. 宝藏(此题未完成)

    区间DP

    AcWing 1068. 环形石子合并
    AcWing 320. 能量项链
    AcWing 479. 加分二叉树
    AcWing 1069. 凸多边形的划分
    AcWing 321. 棋盘分割

    树形DP

    AcWing 1072. 树的最长路径
    AcWing 1073. 树的中心
    AcWing 1075. 数字转换
    AcWing 1074. 二叉苹果树
    AcWing 323. 战略游戏
    AcWing 1077. 皇宫看守

    数位DP

    AcWing 1081. 度的数量
    AcWing 1082. 数字游戏
    AcWing 1083. Windy数
    AcWing 1084. 数字游戏 II
    AcWing 1085. 不要62
    AcWing 1086. 恨7不成妻(此题未完成)

    单调队列优化DP

    AcWing 135. 最大子序和
    AcWing 1087. 修剪草坪
    AcWing 1088. 旅行问题
    AcWing 1089. 烽火传递
    AcWing 1090. 绿色通道
    AcWing 1091. 理想的正方形

    斜率优化DP

    AcWing 300. 任务安排1
    AcWing 301. 任务安排2
    AcWing 302. 任务安排3
    AcWing 303. 运输小猫(此题未完成)

    第二章 搜索 (完成情况:7/25)

    包括Flood Fill、最短路模型、多源BFS、最小步数模型、双端队列广搜、双向广搜、A*、DFS之连通性模型、DFS之搜索顺序、DFS之剪枝与优化、迭代加深、双向DFS、IDA*等内容

    Flood Fill

    AcWing 1097. 池塘计数
    AcWing 1098. 城堡问题
    AcWing 1106. 山峰和山谷

    最短路模型

    AcWing 1076. 迷宫问题
    AcWing 188. 武士风度的牛
    AcWing 1100. 抓住那头牛

    多源BFS

    AcWing 173. 矩阵距离

    最小步数模型

    AcWing 1107. 魔板(此题未完成)

    双端队列广搜

    AcWing 175. 电路维修(此题未完成)

    双向广搜

    AcWing 190. 字串变换(此题未完成)

    A*

    AcWing 178. 第K短路(此题未完成)
    AcWing 179. 八数码(此题未完成)

    DFS之连通性模型

    AcWing 1112. 迷宫(此题未完成)
    AcWing 1113. 红与黑(此题未完成)

    DFS之搜索顺序

    AcWing 1116. 马走日(此题未完成)
    AcWing 1117. 单词接龙(此题未完成)
    AcWing 1118. 分成互质组(此题未完成)

    DFS之剪枝与优化

    AcWing 165. 小猫爬山(此题未完成)
    AcWing 166. 数独(此题未完成)
    AcWing 167. 木棒(此题未完成)
    AcWing 168. 生日蛋糕(此题未完成)

    迭代加深

    AcWing 170. 加成序列(此题未完成)

    双向DFS

    AcWing 171. 送礼物(此题未完成)

    IDA*

    AcWing 180. 排书(此题未完成)
    AcWing 181. 回转游戏(此题未完成)

    第三章 图论 (完成情况:55/58)

    包括单源最短路的建图方式、单源最短路的综合应用、单源最短路的扩展应用、Floyd算法、最小生成树、最小生成树的扩展应用、负环、差分约束、最近公共祖先、强连通分量、双连通分量、二分图、欧拉回路和欧拉路径、拓扑排序等内容

    单源最短路的建图方式

    AcWing 1129. 热浪
    AcWing 1128. 信使
    AcWing 1127. 香甜的黄油
    AcWing 1126. 最小花费
    AcWing 920. 最优乘车
    AcWing 903. 昂贵的聘礼

    单源最短路的综合应用

    AcWing 1135. 新年好
    AcWing 340. 通信线路
    AcWing 342. 道路与航线
    AcWing 341. 最优贸易

    单源最短路的扩展应用

    AcWing 1137. 选择最佳线路
    AcWing 1131. 拯救大兵瑞恩
    AcWing 1134. 最短路计数
    AcWing 383. 观光

    Floyd算法

    AcWing 1125. 牛的旅行
    AcWing 343. 排序
    AcWing 344. 观光之旅
    AcWing 345. 牛站

    最小生成树

    AcWing 1140. 最短网络
    AcWing 1141. 局域网
    AcWing 1142. 繁忙的都市
    AcWing 1143. 联络员
    AcWing 1144. 连接格点

    最小生成树的扩展应用

    AcWing 1146. 新的开始
    AcWing 1145. 北极通讯网络
    AcWing 346. 走廊泼水节
    AcWing 1148. 秘密的牛奶运输

    负环

    AcWing 904. 虫洞
    AcWing 361. 观光奶牛
    AcWing 1165. 单词环

    差分约束

    AcWing 1169. 糖果
    AcWing 362. 区间
    AcWing 1170. 排队布局
    AcWing 393. 雇佣收银员

    最近公共祖先

    AcWing 1172. 祖孙询问
    AcWing 1171. 距离
    AcWing 356. 次小生成树(此题未完成)
    AcWing 352. 闇の連鎖(此题未完成)

    有向图的强连通分量

    AcWing 1174. 受欢迎的牛
    AcWing 367. 学校网络
    AcWing 1175. 最大半连通子图
    AcWing 368. 银河

    无向图的双连通分量

    AcWing 395. 冗余路径
    AcWing 1183. 电力
    AcWing 396. 矿场搭建

    二分图

    AcWing 257. 关押罪犯
    AcWing 372. 棋盘覆盖
    AcWing 376. 机器任务
    AcWing 378. 骑士放置
    AcWing 379. 捉迷藏(此题未完成)

    欧拉回路和欧拉路径

    AcWing 1123. 铲雪车
    AcWing 1184. 欧拉回路
    AcWing 1124. 骑马修栅栏
    AcWing 1185. 单词游戏

    拓扑排序

    AcWing 1191. 家谱树
    AcWing 1192. 奖金
    AcWing 164. 可达性统计
    AcWing 456. 车站分级

    第四章 高级数据结构 (完成情况:20/21)

    包括并查集、树状数组、线段树、可持久化数据结构、平衡树、AC自动机等内容

    并查集

    AcWing 1250. 格子游戏
    AcWing 1252. 搭配购买
    AcWing 237. 程序自动分析
    AcWing 239. 奇偶游戏
    AcWing 238. 银河英雄传说

    树状数组

    AcWing 241. 楼兰图腾
    AcWing 242. 一个简单的整数问题
    AcWing 243. 一个简单的整数问题2
    AcWing 244. 谜一样的牛

    线段树

    AcWing 1275. 最大数
    AcWing 245. 你能回答这些问题吗
    AcWing 246. 区间最大公约数
    AcWing 243. 一个简单的整数问题2
    AcWing 247. 亚特兰蒂斯
    AcWing 1277. 维护序列

    可持久化数据结构

    AcWing 256. 最大异或和
    AcWing 255. 第K小数

    平衡树

    AcWing 253. 普通平衡树
    AcWing 265. 营业额统计

    AC自动机

    AcWing 1282. 搜索关键词
    AcWing 1285. 单词(此题未完成)

    第五章 数学知识 (完成情况:32/35)

    包括筛质数、分解质因数、快速幂、约数个数、欧拉函数、同余、矩阵乘法、组合计数、高斯消元、容斥原理、概率与数学期望、博弈论等内容

    筛质数

    AcWing 1292. 哥德巴赫猜想
    AcWing 1293. 夏洛克和他的女朋友
    AcWing 196. 质数距离

    分解质因数

    AcWing 197. 阶乘分解

    快速幂

    AcWing 1289. 序列的第k个数
    AcWing 1290. 越狱

    约数个数

    AcWing 1291. 轻拍牛头
    AcWing 1294. 樱花
    AcWing 198. 反素数
    AcWing 200. Hankson的趣味题

    欧拉函数

    AcWing 201. 可见的点
    AcWing 220. 最大公约数

    同余

    AcWing 203. 同余方程
    AcWing 222. 青蛙的约会
    AcWing 202. 最幸运的数字
    AcWing 1298. 曹冲养猪

    矩阵乘法

    AcWing 1303. 斐波那契前 n 项和
    AcWing 1304. 佳佳的斐波那契
    AcWing 1305. GT考试(此题未完成)

    组合计数

    AcWing 1307. 牡牛和牝牛
    AcWing 1308. 方程的解
    AcWing 1309. 车的放置
    AcWing 1310. 数三角形
    AcWing 1312. 序列统计
    AcWing 1315. 网格
    AcWing 1316. 有趣的数列

    高斯消元

    AcWing 207. 球形空间产生器
    AcWing 208. 开关问题

    容斥原理

    AcWing 214. Devu和鲜花
    AcWing 215. 破译密码(此题未完成)

    概率与数学期望

    AcWing 217. 绿豆蛙的归宿
    AcWing 218. 扑克牌

    博弈论

    AcWing 1319. 移棋子游戏
    AcWing 1321. 取石子
    AcWing 1322. 取石子游戏(此题未完成)

    第六章 基础算法 (完成情况:12/12)

    包括位运算、递推与递归、前缀和与差分、二分、排序、RMQ等内容

    位运算

    AcWing 90. 64位整数乘法

    递推与递归

    AcWing 95. 费解的开关
    AcWing 97. 约数之和
    AcWing 98. 分形之城

    前缀和与差分

    AcWing 99. 激光炸弹
    AcWing 100. 增减序列

    二分

    AcWing 102. 最佳牛围栏
    AcWing 113. 特殊排序

    排序

    AcWing 105. 七夕祭
    AcWing 106. 动态中位数
    AcWing 107. 超快速排序

    RMQ

    AcWing 1273. 天才的记忆

    展开全文
  • 池塘计数AcWing 1098. 城堡问题AcWing 1106. 山峰和山谷最短路模型AcWing 1076. 迷宫问题AcWing 188. 武士风度的牛AcWing 1100. 抓住那头牛多源BFSAcWing 173. 矩阵距离最小步数模型AcWing 1107. 魔板双端队列广搜...

    BFS

    Flood Fill

    AcWing 1097. 池塘计数

    /*
    基础课回忆:
    搜索:DFS BFS
    BFS:
        最短距离(AcWing 844. 走迷宫):给一个地图(二维矩阵),定义起点终点,问从起点走到终点的最短距离
        最小步数(AcWing 845. 八数码):对地图本身操作,求其中一种状态(地图)变成另外一种地图的最小步数,把整个地图看成一个点
    BFS特点:
        1.求最小
        2.基于迭代,不会爆栈(相对于DFS,当一个问题层数很深,但节点个数不深,优先选择BFS)
        
    Flood Fill算法:可以在线性时间复杂度内,找到某个点所在的连通块
    
    地图连通有两种:四连通,八连通
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 1010, M = N * N;
    
    int n, m;
    char g[N][N];
    PII q[M];//用Flood Fill算法遍历二维地图,一般都要存下标
    bool st[N][N];//宽搜都需要判重,标记数组,防止重复遍历某个点
    
    void bfs(int sx, int sy)
    {
        int hh = 0, tt = 0;//数组模拟队列
        q[0] = {sx, sy};
        st[sx][sy] = true;
    
        while (hh <= tt)
        {
            PII t = q[hh ++ ];
    
            for (int i = t.x - 1; i <= t.x + 1; i ++ )//八连通,两重循环,中间点挖掉
                for (int j = t.y - 1; j <= t.y + 1; j ++ )
                {
                    if (i == t.x && j == t.y) continue;
                    if (i < 0 || i >= n || j < 0 || j >= m) continue;
                    if (g[i][j] == '.' || st[i][j]) continue;
    
                    q[ ++ tt] = {i, j};
                    st[i][j] = true;
                }
        }
    }
    
    int main()
    {
        cin>>n>>m;//读入数据较大,推荐用scanf读
        for (int i = 0; i < n; i ++ ) cin>>g[i];//读入每一行
    
        int cnt = 0;//池塘数目
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == 'W' && !st[i][j])//宽搜判断条件一般都很长,想清楚
                {
                    bfs(i, j);//输入起点
                    cnt ++ ;
                }
    
        cout<<cnt<<endl;
    
        return 0;
    }
    

    AcWing 1098. 城堡问题

    /*
    找到所有连通块:Flood Fill  
    但是输入比较复杂,依次输入每个小方块周围墙的情况,可以用二进制编码表示,判断第0到3位哪一位为1
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 55, M = N * N;
    
    int n, m;
    int g[N][N];
    PII q[M];
    bool st[N][N];
    
    int bfs(int sx, int sy)
    {
        int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
    
        int hh = 0, tt = 0;
        int area = 0;
    
        q[0] = {sx, sy};
        st[sx][sy] = true;
    
        while (hh <= tt)
        {
            PII t = q[hh ++ ];
            area ++ ;
    
            for (int i = 0; i < 4; i ++ )
            {
            for(int i=0;i<4;i++){
                int a=t.x+dx[i], b=t.y+dy[i];
                if(a>=0&&a<n&&b>=0&&b<m&&st[a][b]==false&&!(g[t.x][t.y]>>i&1)){
                    q[++tt]={a,b};
                    st[a][b]=true;
                }
                // if (a < 0 || a >= n || b < 0 || b >= m) continue;
                // if (st[a][b]) continue;
                // if (g[t.x][t.y] >> i & 1) continue;//二进制表示第i位是否为1
    
                // q[ ++ tt] = {a, b};
                // st[a][b] = true;
            }
            }
        }
    
        return area;
    }
    
    int main()
    {
        cin >> n >> m;//输入较少,cin
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                cin >> g[i][j];
    
        int cnt = 0, area = 0;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (!st[i][j])
                {
                    area = max(area, bfs(i, j));
                    cnt ++ ;
                }
    
        cout << cnt << endl;
        cout << area << endl;
    
        return 0;
    }
    

    AcWing 1106. 山峰和山谷

    /*
    八连通,统计连通块与周围关系
    */
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    const int N=1010;
    
    #define x first
    #define y second
    typedef pair<int,int> PII;
    
    int n;
    int h[N][N];
    PII q[N*N];
    bool st[N][N];
    
    void bfs(int sx,int sy,bool& has_higher,bool& has_lower){
        int hh=0,tt=0;
        q[0]={sx,sy};
        st[sx][sy]=true;
        
        while(hh<=tt){
            auto t=q[hh++];
            
            for(int i=t.x-1;i<=t.x+1;i++){
                for(int j=t.y-1;j<=t.y+1;j++){
                    if(i==t.x&&j==t.y) continue;
                    if(i<0||i>=n||j<0||j>=n) continue;
                    if(h[i][j]!=h[t.x][t.y]){// 山脉的边界
                        if(h[i][j]>h[t.x][t.y]) has_higher=true;
                        else has_lower=true;
                    }
                    else if(!st[i][j]){
                        q[++tt]={i,j};
                        st[i][j]=true;
                    }
                }
            }
        }
    }
    
    int main(){
        cin>>n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>h[i][j];
            }
        }
        
        int peak=0,valley=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!st[i][j]){
                    //统计当前格子所在连通块与周围格子的关系,两个变量为周围是否有比它高或低的,只有为false时才能完全确定周围没有比它高或低的
                    bool has_higher=false,has_lower=false;
                    bfs(i,j,has_higher,has_lower);//同一个山脉可能既是山峰又是山谷,所以都要判断
                    if(!has_higher) peak++;
                    if(!has_lower) valley++;//别加else,这样就2选1了
                }
            }
        }
        
        cout<<peak<<' '<<valley<<endl;
        return 0;
    }
    

    最短路模型

    AcWing 1076. 迷宫问题

    /*
    当所有边权重相等时,用宽搜从起点开始搜就可以得到所有点的单元最短路
    走迷宫题目扩展,不止要求出最短路长度,还要求出方案路径
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 1010, M = N * N;
    
    int n;
    int g[N][N];
    PII q[M];
    PII pre[N][N];//从st数组扩展而来,保存每一个格子从哪儿走过来的
    
    void bfs(int sx, int sy)
    {
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
        int hh = 0, tt = 0;
        q[0] = {sx, sy};
    
        memset(pre, -1, sizeof pre);
        pre[sx][sy] = {0, 0};
        while (hh <= tt)
        {
            PII t = q[hh ++ ];
    
            for (int i = 0; i < 4; i ++ )
            {
                int a = t.x + dx[i], b = t.y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= n) continue;
                if (g[a][b]) continue;
                if (pre[a][b].x != -1) continue;
    
                q[ ++ tt] = {a, b};
                pre[a][b] = t;
            }
        }
    }
    
    int main(){
        cin>>n;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>g[i][j];
            }
        }
        
        bfs(n-1,n-1);//到这搜索是为了最后输出时正向输出
        
        PII end(0,0);
        
        while(true){
            cout<<end.x<<' '<<end.y<<endl;
            if(end.x==n-1&&end.y==n-1) break;
            end=pre[end.x][end.y];
        }
        
        return 0;
    }
    

    AcWing 188. 武士风度的牛

    /*
    给定一个图,从起点走到终点,每条边权值为1,所以可以用BFS做,
    走迷宫题目的简单扩展,走迷宫是只能走上下左右四个方向,这道题扩展成走日字型的八个方向
    
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 155, M = N * N;
    
    int n, m;
    char g[N][N];
    PII q[M];
    int dist[N][N];
    //很多时候不用先实现细节,先把整个思路整理好
    int bfs(int sx, int sy)
    {
        int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
        int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    
        int hh = 0, tt = 0;
        q[0] = {sx, sy};
    
        memset(dist, -1, sizeof dist);
        dist[sx][sy] = 0;
    
        while (hh <= tt)
        {
            auto t = q[hh ++ ];
            if(g[t.x][t.y]=='H') return dist[t.x][t.y];
            
            for (int i = 0; i < 8; i ++ )
            {
                int a = t.x + dx[i], b = t.y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m) continue;
                if (g[a][b] == '*') continue;
                if (dist[a][b] != -1) continue;
    
                dist[a][b] = dist[t.x][t.y] + 1;
                q[ ++ tt] = {a, b};
            }
        }
    
        return -1;
    }
    
    int main()
    {
        cin >> m >> n;//这道题先输入列数,再输入行数,一定看清楚
    
        for (int i = 0; i < n; i ++ ) cin >> g[i];
    
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == 'K')
                    cout << bfs(i,j) << endl;
    
        return 0;
    }
    

    AcWing 1100. 抓住那头牛

    /*
    给定一个图,从起点走到终点,每条边权值为1,所以可以用BFS做
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e5 + 10;//步数可能大于数据范围
    
    int n, k;
    int q[N];
    int dist[N];
    
    int bfs()
    {
        memset(dist, -1, sizeof dist);
        dist[n] = 0;
        q[0] = n;
    
        int hh = 0, tt = 0;
    
        while (hh <= tt)
        {
            int t = q[hh ++ ];
    
            if (t == k) return dist[k];//一定有解
    
            if (t + 1 < N && dist[t + 1] == -1)
            {
                dist[t + 1] = dist[t] + 1;
                q[ ++ tt] = t + 1;
            }
            if (t - 1 >= 0 && dist[t - 1] == -1)
            {
                dist[t - 1] = dist[t] + 1;
                q[ ++ tt] = t - 1;
            }
            if (t * 2 < N && dist[t * 2] == -1)
            {
                dist[t * 2] = dist[t] + 1;
                q[ ++ tt] = t * 2;
            }
        }
    
        return -1;
    }
    
    int main()
    {
        cin >> n >> k;
    
        cout << bfs() << endl;
    
        return 0;
    }
    

    多源BFS

    AcWing 173. 矩阵距离

    /*
    求每一个位置到所有1的最短距离,到最近的1的距离
    当只有一个起点时,把这个起点放入队列,往外扩展
    多个起点时,朴素做法是分别以每个起点遍历一遍取最小值
    优化:加一个虚拟源点之后转化成单源最短路问题
    这里不需要建立虚拟源点,只需要在最开始时候把所有是1的位置初始化为0,然后把这些是1的位置添加到队列里面,也就是队列第一层
    存的是所有起点,距离为1的点,后面部分跟一般搜索完全一样
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 1010, M = N * N;
    
    int n, m;
    char g[N][N];
    PII q[M];
    int dist[N][N];
    
    void bfs()
    {
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
        memset(dist, -1, sizeof dist);
    
        int hh = 0, tt = -1;
        for(int i = 0; i < n;i ++) 
            for(int j = 0; j < m;j ++)
                if (g[i][j] == '1')
                {
                    dist[i][j] = 0;
                    q[ ++ tt] = {i, j};
                }
    
        while (hh <= tt)
        {
            auto t = q[hh ++ ];
    
            for (int i = 0; i < 4; i ++ )
            {
                int a = t.x + dx[i], b = t.y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m) continue;
                if (dist[a][b] != -1) continue;
    
                dist[a][b] = dist[t.x][t.y] + 1;
                q[ ++ tt] = {a, b};
            }
        }
    }
    
    int main()
    {
        cin>>n>>m;
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);//每行输入数字之间没有空格,用字符串读入
    
        bfs();
    
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < m; j ++ ) cout<<dist[i][j]<<' ';
            puts("");
        }
    
        return 0;
    }
    

    最小步数模型

    AcWing 1107. 魔板

    /*
    如何存储状态:哈希法
    思路简单,代码不好写
    先把12345678这个状态放入队头,然后用宽搜搜所有状态,直到终点为止,每一次扩展时,分别做abc三种操作,得到三个字符串
    判断是否哪个字符串之前搜到过,如果没有搜到过,更新距离,放入队列
    记录方案:
    记录每一个状态是由哪个状态转移过来的,这样就可以由终点倒推到起点
    如何保证最小字典序输出:
    扩展每个状态时,按照ABC的顺序
    三个操作需要分别写
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <unordered_map>
    #include <queue>
    
    using namespace std;
    
    char g[2][4];
    unordered_map<string, pair<char, string>> pre;
    //存下来每一个状态怎么样转移过来的,用pair来存,因为不只是要知道哪个状态转移,还要知道怎么样转移
    unordered_map<string, int> dist;//存下来每一个状态的步数,用哈希表来存
    
    void set(string state)
    {//把字符串放入原来二维数组中
        for (int i = 0; i < 4; i ++ ) g[0][i] = state[i];
        for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i];
    }
    
    string get()
    {//set的逆操作
        string res;
        for (int i = 0; i < 4; i ++ ) res += g[0][i];
        for (int i = 3; i >= 0; i -- ) res += g[1][i];
        return res;
    }
    
    string move0(string state)
    {
        set(state);
        for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);
        return get();
    }
    
    string move1(string state)
    {
        set(state);
        int v0 = g[0][3], v1 = g[1][3];
        for (int i = 3; i >= 0; i -- )
        {
            g[0][i] = g[0][i - 1];
            g[1][i] = g[1][i - 1];
        }
        g[0][0] = v0, g[1][0] = v1;
        return get();
    }
    
    string move2(string state)
    {
        set(state);
        int v = g[0][1];
        g[0][1] = g[1][1];
        g[1][1] = g[1][2];
        g[1][2] = g[0][2];
        g[0][2] = v;
        return get();
    }
    
    int bfs(string start, string end)
    {
        if (start == end) return 0;
    
        queue<string> q;
        q.push(start);
        dist[start] = 0;
    
        while (!q.empty())
        {
            auto t = q.front();
            q.pop();
    
            string m[3];
            m[0] = move0(t);
            m[1] = move1(t);
            m[2] = move2(t);
    
            for (int i = 0; i < 3; i ++ )
                if (!dist.count(m[i]))
                {
                    dist[m[i]] = dist[t] + 1;
                    pre[m[i]] = {'A' + i, t};
                    q.push(m[i]);
                    if (m[i] == end) return dist[end];
                }
        }
    
        return -1;
    }
    
    int main()
    {
        int x;
        string start, end;
        for (int i = 0; i < 8; i ++ )
        {
            cin >> x;
            end += char(x + '0');//把数字i变成字符i
        }
    
        for (int i = 1; i <= 8; i ++ ) start += char('0' + i);
    
        int step = bfs(start, end);
    
        cout << step << endl;
    
        string res;
        while (end != start)
        {
            res += pre[end].first;
            end = pre[end].second;
        }
    
        reverse(res.begin(), res.end());
    
        if (step > 0) cout << res << endl;
    
        return 0;
    }
    

    双端队列广搜

    AcWing 175. 电路维修

    /*
    求从左上角到右下角的最短路,最短路中边权有两种
    如果可以直接走到的话,不需要旋转,旋转次数为0,边权为0,如果需要旋转才能走到的话,旋转次数为1,边权为1
    等价于给了一张无向图,图中有两种边,边权为0或1,从起点到终点的最短路径
    之前的题是所有边权重一样,直接BFS求出最短路
    双向队列与一般宽搜相比,一般宽搜是取出队头之后,把所有能从队头扩展的元素放入队尾
    而双向队列是判断从队头取出来的元素,边权重是0还是1,如果扩展出来的边权重是0就插到队头,否则插到队尾
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <deque>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 510, M = N * N;
    
    int n, m;
    char g[N][N];
    int dist[N][N];
    bool st[N][N];
    
    int bfs()//之前每个点只会入队一次,这里由于有0的边权存在,所有每个点可能入队多次
    {
        memset(dist, 0x3f, sizeof dist);
        memset(st, 0, sizeof st);
        dist[0][0] = 0;
        deque<PII> q;
        q.push_back({0, 0});
    
        char cs[] = "\\/\\/";//存一下四个方向什么方向才是通路\/\/  \是转义字符所有前面再加一个\
        int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
        int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};//判断每个方向的边,注意格点坐标和字符在所给二维字符数组坐标
    
        while (q.size())
        {
            PII t = q.front();
            q.pop_front();
    
            if (st[t.x][t.y]) continue;//和dijistar一样,判断之前是否算过它
            st[t.x][t.y] = true;
    
            for (int i = 0; i < 4; i ++ )
            {
                int a = t.x + dx[i], b = t.y + dy[i];
                if (a < 0 || a > n || b < 0 || b > m) continue;//注意格点长度比格子长度多1
    
                int ca = t.x + ix[i], cb = t.y + iy[i];
                int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);
    
                if (d < dist[a][b])
                {
                    dist[a][b] = d;
    
                    if (g[ca][cb] != cs[i]) q.push_back({a, b});
                    else q.push_front({a, b});
                }
            }
        }
    
        return dist[n][m];
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T -- )
        {
            scanf("%d%d", &n, &m);
            for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
    
            int t = bfs();
    
            if (t == 0x3f3f3f3f) puts("NO SOLUTION");
            else printf("%d\n", t);
        }
    
        return 0;
    }
    

    双向广搜

    AcWing 190. 字串变换

    /*
    把一个字符串看成一个单独的状态,把它所有可以经过一步变换变成的状态看作从这个状态向变到的状态连一条长度为1的边
    从而转变为图论问题,从起点走到终点最少需要走几步
    数据范围:
    字符串长度的上限为20,最多6个规则,每一个规则都可能是从每一个字母开始,最坏情况下20*6(变换方式)^10(最多变换十次)
    如果单向搜索会超时,那就从起点和终点两方同时开始搜
    BFS优化:双向广搜一般用在最小步数模型(指数级别)中,在最短路模型,Flood Fill一般用不到,因为他们搜的点数量一般不大
    两个方向同时搜索,而不是一个方向搜到另外一个方向
    最坏情况下20*6^10->2*20*6^5
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <unordered_map>
    #include <queue>
    
    using namespace std;
    
    const int N = 6;
    
    int n;
    string a[N], b[N];
    
    int extend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int>& db, string a[], string b[])
    {
        for (int k = 0, sk = q.size(); k < sk; k ++ )//每次每边扩展完整一层
        {
            string t = q.front();
            q.pop();
            //开始扩展,两个维度考虑
            for (int i = 0; i < t.size(); i ++ )//扩展起点
                for (int j = 0; j < n; j ++ )//枚举规则
                    if (t.substr(i, a[j].size()) == a[j])//匹配规则
                    {
                        string state = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
                        //判断此时尝试扩展的状态是否已经被这个方向或另外一个方向扩展
                        if (da.count(state)) continue;//判断此时尝试扩展的状态之前已经被扩展过,只记录第一次
                        if (db.count(state)) return da[t] + 1 + db[state];//此时枚举到了两个方向重合的地方
                        da[state] = da[t] + 1;
                        q.push(state);
                    }
        }
    
        return 11;
    }
    
    int bfs(string A, string B)
    {
        queue<string> qa, qb;//由于是两个方向,所以要建两个方向的队列
        unordered_map<string, int> da, db;
        qa.push(A), da[A] = 0;//从起点开始搜索,存储每个点到起点的距离
        qb.push(B), db[B] = 0;
    
        while (qa.size() && qb.size())//如果只有一方还有,另一方没了,说明AB不连通
        {
            int t;//都存在情况下,判断哪个方向队列长度更小,说明这个方向空间更小,就朝这个方向扩展
            if (qa.size() <= qb.size()) t = extend(qa, da, db, a, b);//扩展qa a的距离 b的距离 把a变成b
            else t= extend(qb, db, da, b, a);
    
            if (t <= 10) return t;
        }
    
        return 11;
    }
    
    int main()
    {
        string A, B;
        cin >> A >> B;
        while (cin >> a[n] >> b[n]) n ++ ;
    
        int step = bfs(A, B);
        if (step > 10) puts("NO ANSWER!");
        else cout<<step<<endl;
    
        return 0;
    }
    

    A*

    AcWing 178. 第K短路

    /*
    每条最短路中至少要包含一条边,所以当s==t时,k++
    如何枚举到所有路线:
    每次从0开始扩展,每次要把当前这个点能扩展到的点全部加进来,求最短路时是只有能更新它的时候才加进来,但这里是所有加进来
    因为不只是求最短路而是第k短路,从所有路径中找到第k小
    搜索空间非常庞大
    估价函数(小于等于真实距离,越接近越好):
    当前点到终点的最短距离,这个可以反向求终点到每个点的最短距离,反向图跑dijkstra算法
    如何求出第k短路:
    当终点第一次从队列中弹出来时,一定是最小值(第一小),第k次弹出来就是第k小
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int, int> PII;
    typedef pair<int, PII> PIII;
    
    const int N = 1010, M = 200010;//因为要建反图,两倍边
    
    int n, m, S, T, K;//点数,边数,起点S,终点T和第K短路
    int h[N], rh[N], e[M], w[M], ne[M], idx;
    int dist[N], cnt[N];
    bool st[N];
    
    void add(int h[], int a, int b, int c)
    {
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    void dijkstra()
    {
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        heap.push({0, T});
    
        memset(dist, 0x3f, sizeof dist);
        dist[T] = 0;
    
        while (heap.size())
        {
            auto t = heap.top();
            heap.pop();
    
            int ver = t.y;
            if (st[ver]) continue;
            st[ver] = true;
    
            for (int i = rh[ver]; ~i; i = ne[i])
            {
                int j = e[i];
                if (dist[j] > dist[ver] + w[i])
                {
                    dist[j] = dist[ver] + w[i];
                    heap.push({dist[j], j});
                }
            }
        }
    }
    
    int astar()
    {
        priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
        heap.push({dist[S], {0, S}});//起点估价,
    
        while (heap.size())
        {
            auto t = heap.top();
            heap.pop();
    
            int ver = t.y.y, distance = t.y.x;
            cnt[ver] ++ ;
            if (cnt[T] == K) return distance;
    
            for (int i = h[ver]; ~i; i = ne[i])
            {//扩展所有边
                int j = e[i];
                if (cnt[j] < K)
                    heap.push({distance + w[i] + dist[j], {distance + w[i], j}});
            }
        }
    
        return -1;
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        memset(h, -1, sizeof h);
        memset(rh, -1, sizeof rh);
    
        for (int i = 0; i < m; i ++ )
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(h, a, b, c);
            add(rh, b, a, c);
        }
        scanf("%d%d%d", &S, &T, &K);
        if (S == T) K ++ ;
    
        dijkstra();
        printf("%d\n", astar());
    
        return 0;
    }
    

    AcWing 179. 八数码

    /*
    A*算法解决的问题和双向广搜一样
    这个算法正确的条件:有解且估计距离<=真实距离(这里都是当前点到终点的距离),越接近越好
    它只能保证当终点出队时,终点距离最小,并不能保证中间的点最小
    启发函数:从起点开始搜,遍历很少的状态搜到终点
    基本流程:
        把BFS中的队列换成优先队列,给每个点一个估计值,按照估计值排序,每次选择一个我们认为最好的点扩展
        特别像dijistra算法,注意A*算法能处理的图当中的边权任意即可,绝大多数情况边权非负,但不能有负权回路,不要求为1
        dijkstra算法可以看做所有估计距离都取0的算法,本质上没什么关系,只是形式上比较接近
        while(!q.empty()){
            t<-取出优先队列队头(小根堆)(排序关键字是两个距离相加)
            当终点第一次出队时,break
            除了存真实距离之外,还需要存真实距离(从起点到当前点)+估价距离(从当前点到终点的估计距离)
            开始扩展
            for t的所有邻边
                将邻边入队
        }
    宽搜:
    BFS:每个状态只会入队一次,所以在入队时候判重
    djikstra:一旦出队就是正确的,所以可以在出队时候判重
    A*:出队时候都不能判重,除了终点外,其他点出来一次,更新一次
    spfa:搜索空间可能比较多,上面是尽量减少搜索空间
    */
    /*
    朴素见基础课
    八数码有解<=>逆序对数量为偶数
    估价函数如何设计:
    观察每次移动只会把一个数移动一次,因此股价函数可以取每一个数与它真实位置之间的曼哈顿距离
    当前状态中每个数与它的目标位置的曼哈顿距离之和
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <unordered_map>
    
    using namespace std;
    
    int f(string state)
    {//估计函数,求曼哈顿距离之和
        int res = 0;
        for (int i = 0; i < state.size(); i ++ )
            if (state[i] != 'x')
            {
                int t = state[i] - '1';
                //转换成数值,减去1是因为题目中从给定的数从1开始,−‘1′后代表数字1映射后是0,数字2是映射后是1.....依次类推即可。
                res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
            }
        return res;
    }
    
    string bfs(string start)
    {
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        char op[4] = {'u', 'r', 'd', 'l'};
    
        string end = "12345678x";
        unordered_map<string, int> dist;//记录距离
        unordered_map<string, pair<string, char>> prev;//记录前驱状态,由哪个状态经过什么操作转移过来的
        priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> heap;
        //优先队列中存的是pair,第一维是估计距离,第二维是状态,因为是小根堆,所以加两个参数
    
        heap.push({f(start), start});
        dist[start] = 0;
    
        while (heap.size())
        {
            auto t = heap.top();
            heap.pop();
    
            string state = t.second;
    
            if (state == end) break;
    
            int step = dist[state];
            int x, y;
            for (int i = 0; i < state.size(); i ++ )
                if (state[i] == 'x')
                {
                    x = i / 3, y = i % 3;
                    break;
                }//找到xy的横纵坐标
            //扩展
            string source = state;//为了方便恢复现场先把原状态存下来
            for (int i = 0; i < 4; i ++ )
            {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < 3 && b >= 0 && b < 3)
                {
                    swap(state[x * 3 + y], state[a * 3 + b]);//先交换看一下,判断新的状态距离是否更小
                    if (!dist.count(state) || dist[state] > step + 1)
                    //如果它之前没有被扩展过,或者虽然被扩展过,但距离较大,需要被更新优化
                    {
                        dist[state] = step + 1;
                        prev[state] = {source, op[i]};
                        heap.push({dist[state] + f(state), state});
                    }
                    swap(state[x * 3 + y], state[a * 3 + b]);
                }
            }
        }
    
        string res;//方案
        while (end != start)
        {
            res += prev[end].second;
            end = prev[end].first;
        }
        reverse(res.begin(), res.end());
        return res;
    }
    
    int main()
    {
        string g, c, seq;
        while (cin >> c)
        {
            g += c;//初始状态
            if (c != "x") seq += c;//序列
        }
    
        int t = 0;//求逆序对数量
        for (int i = 0; i < seq.size(); i ++ )
            for (int j = i + 1; j < seq.size(); j ++ )
                if (seq[i] > seq[j])
                    t ++ ;
    
        if (t % 2) puts("unsolvable");//逆序对为奇数一定无解
        else cout << bfs(g) << endl;
    
        return 0;
    }
    

    DFS

    DFS之连通性模型

    AcWing 1112. 迷宫

    /*
    BFS:横向扩展,一层一层搜 队列
    DFS:纵向扩展,一条道走到底 栈
    连通性模型(两个方法都可以做):Flood Fill(搜连通块),图与树的遍历
    这道题BFS,DFS都可以,BFS还可以知道最短距离,DFS只能判断是否连通(但是代码短很多,BFS需要手写队列,DFS可以直接用系统栈)
    注意是否会爆栈,递归改成非递归
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 110;
    //不需要写pair
    int n;
    char g[N][N];
    int xa, ya, xb, yb;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    bool st[N][N];//判重数组
    
    bool dfs(int x, int y)
    {
        if (g[x][y] == '#') return false;
        if (x == xb && y == yb) return true;
    
        st[x][y] = true;//不需要恢复现场,标记保证每个点只遍历一次
    
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= n) continue;
            if (st[a][b]) continue;
            if (dfs(a, b)) return true;
        }
    
        return false;
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T -- )
        {
            scanf("%d", &n);
            for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
            scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
    
            memset(st, 0, sizeof st);
            if (dfs(xa, ya)) puts("YES");
            else puts("NO");
        }
    
        return 0;
    }
    

    AcWing 1113. 红与黑

    /*
    求当前这个点的连通块 Flood Fill DFS实现
    DFS缺点:搜索层数较多时可能爆栈
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 25;
    
    int n, m;
    char g[N][N];
    bool st[N][N];
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    int dfs(int x, int y)
    {
        int cnt = 1;
    
        st[x][y] = true;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (g[a][b] != '.') continue;
            if (st[a][b]) continue;
    
            cnt += dfs(a, b);
        }
    
        return cnt;
    }
    
    int main()
    {
        while (cin >> m >> n, n || m)//先输入列数,再输入行数
        {
            for (int i = 0; i < n; i ++ ) cin >> g[i];
    
            int x, y;//确定起点 
            //DFS两种模型:人体内部从哪儿到哪儿;人当做一个整体,人能到哪儿。这个影响到深搜时是否要恢复现场
            //如果是第一种人体内部的话,为了保证每个点只能搜一次,不能恢复现场
            //第二种的话,一定要恢复原状
            for (int i = 0; i < n; i ++ )
                for (int j = 0; j < m; j ++ )
                    if (g[i][j] == '@')
                    {
                        x = i;
                        y = j;
                    }
    
            memset(st, 0, sizeof st);
            cout << dfs(x, y) << endl;
        }
    
        return 0;
    }
    

    DFS之搜索顺序

    AcWing 1116. 马走日

    /*
    按照哪种顺序搜可以把全部状态搜出来
    最开始在起点,尝试分别枚举最多可跳的八个方向,如果哪个方向可以走的话,继续
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 10;
    
    int n, m;
    bool st[N][N];//每个位置是否走过
    int ans;
    int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
    
    void dfs(int x, int y, int cnt)
    {
        if (cnt == n * m)
        {
            ans ++ ;
            return;
        }
        st[x][y] = true;
    
        for (int i = 0; i < 8; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;//判断这一个点在这条路径上是否被走过,但是要恢复现场是因为这个点可以被不同的路径走过
            dfs(a, b, cnt + 1);
        }
    
        st[x][y] = false;
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T -- )
        {
            int x, y;
            scanf("%d%d%d%d", &n, &m, &x, &y);
    
            //memset(st, 0, sizeof st);//这里初始化可以不用做,因为每次都要恢复现场
            ans = 0;
            dfs(x, y, 1);//当前正在搜第几个点
    
            printf("%d\n", ans);
        }
    
        return 0;
    }
    

    AcWing 1117. 单词接龙

    /*
    先判断任意两个单词能否接到一块,可以的话就表示两者之间有一条边,先预处理一下二维的邻接矩阵,表示点之间的邻接关系
    预处理之后就可以暴搜,枚举所有情况,树的最大深度为40,因为每个单词最多用两次,单词数最多20 
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 21;
    
    int n;
    string word[N];
    int g[N][N];//初始化任意两个单词是否有边,如果相连,存储最小重合长度
    int used[N];//每个单词用了多少次
    int ans;
    
    void dfs(string dragon, int last)
    {
        ans = max((int)dragon.size(), ans);
    
        used[last] ++ ;
    
        for (int i = 0; i < n; i ++ )//下一个单词填哪个
            if (g[last][i] && used[i] < 2)//如果第last个单词后面可以接第i个单词,并且,第i个单词没用到两次
                dfs(dragon + word[i].substr(g[last][i]), i);
    
        used[last] -- ;//恢复现场
    }
    
    int main()
    {
        cin >> n;//测试数据单组
        for (int i = 0; i < n; i ++ ) cin >> word[i];
        char start;
        cin >> start;
    
        for (int i = 0; i < n; i ++ )//初始化任意两个单词是否有边
            for (int j = 0; j < n; j ++ )
            {
                string a = word[i], b = word[j];
                for (int k = 1; k < min(a.size(), b.size()); k ++ )//重合长度必须大于等于1,且严格小于两个串的长度
                    if (a.substr(a.size() - k, k) == b.substr(0, k))
                    {
                        g[i][j] = k;
                        break;//要接龙最长,重合部分越短越好,所以从小到大枚举
                    }
            }
    
        for (int i = 0; i < n; i ++ )
            if (word[i][0] == start)
                dfs(word[i], i);//i表示当前接龙的最后一个单词是第i个单词
    
        cout << ans << endl;
    
        return 0;
    }
    

    AcWing 1118. 分成互质组

    /*
    转化成图论问题,如果两个数之间不互质连一条边,表示有关系,转化成图当中最少分为多少组,使得每一组内没有边
    像仇恨,讨厌关系,小孩之间闹矛盾,有矛盾就连边,比较经典问题
    简单做法:核心是如何枚举所有情况,找到最优解
    一个组一个组枚举,第一个组中该选谁
    第一种方案:把某个数加到最后一组(之前的组已经全部枚举完,尽可能让分支数量少,搜索空间小)
    第二种方案:新开一个组
    (一般出成暴搜的都是np完全问题,否则考虑DP,贪心解法)
    优化:
    1.当可以做两个操作时,就做第一个操作,只有当所有数都不能加到最后一个组时再新开辟一个组
    2.考虑哪些数要放到当前组时,这是一个组合问题,不是排列问题,要按照组合方式搜索,与排列顺序无关,为了不重复搜索
      像先搜到123,再搜到132这种,我们人为定义一个组内顺序,按照下标从小到大顺序往组里添数,只需要在搜索时传入一个参数
      表示当前从哪个位置开始搜,很多时候只需要枚举组合情况,不需要枚举排列情况
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 10;
    
    int n;
    int p[N];
    int group[N][N];//最多N组,每一组要分别记下来
    bool st[N];//判重数组,当前每个数是否被用过
    int ans = N;//答案最坏情况是N,每个数单独一组
    
    int gcd(int a, int b)
    {//判断两个数互质:欧几里得算法
        return b ? gcd(b, a % b) : a;
    }
    
    bool check(int group[], int gc, int i)
    {
        for (int j = 0; j < gc; j ++ )
            if (gcd(p[group[j]], p[i]) > 1)
                return false;//不是互质
        return true;
    }
    //第几组,当前组内下标,当前一共搜了多少个元素,当前可以从哪个元素开始搜
    void dfs(int g, int gc, int tc, int start)
    {
        if (g >= ans) return;//如果当前组数量已经大于之前的一个可能的解,那这样继续搜索一定不是最优解,提前结束
        if (tc == n) ans = g;//全部搜完
    
        bool flag = true;//先假设不能添加元素,再探索每个元素,只要有一个可以添加,就加进去,然后设为false
        for (int i = start; i < n; i ++ )//如果当前遍历元素没有被用过,并且当前组内所有元素与第i个数是互质的,就可以用
            if (!st[i] && check(group[g], gc, i))
            {
                st[i] = true;
                group[g][gc] = i;
                dfs(g, gc + 1, tc + 1, i + 1);
                st[i] = false;//恢复现场
    
                flag = false;//表示当前组内能否添加元素,能添加就设为false
            }
    
        if (flag) dfs(g + 1, 0, tc, 0);//每个元素都遍历完了都添加不了,只能新开一组,从下标为0开始探索
    }
    
    int main()
    {
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> p[i];
    
        dfs(1, 0, 0, 0);//先搜第一组,组内有0个元素,当前已经搜了0个元素,从0号下标开始搜
    
        cout << ans << endl;
    
        return 0;
    }
    

    DFS之剪枝与优化

    AcWing 165. 小猫爬山

    /*
    深搜与宽搜不管内部还是外部搜索都可以对应一条搜索树,树种节点表示方案,搜索剪枝是不一定要走到头才能知道方案不合法
    可能走到一半就能知道方案不合法,提前判断退出,对应子树不用搜索,提高效率
    常用的剪枝方式:
        1.优化搜索顺序:一般情况下优先搜索分支较少(选择,策略较少)的节点
        2.排除等效冗余:比如搜索组合数(不考虑顺序,不搜索重复状态,按照组合方式搜索)
        3.可行性剪枝:搜索过程中搜到一半发现不合法,提前退出
        4.最优性剪枝:搜索过程中搜到一半发现无论如何都会比当前搜到的最优解要差
        5.记忆化搜索(DP)
    n比较小,数据范围提示用暴力搜索来做
    暴搜第一点是考虑搜索顺序枚举所有方案
    从前往后依次枚举每只小猫,每次枚举当前小猫应该放在哪辆车上(已有的车或新开一辆),递归n层 
    每递归一层,把一只小猫安排好,放完之后看下当前用了几辆车,全局所有方案取最小
    时间复杂度不太好估计,暴力搜索都这样,指数级别,具体多少不太好算
    这道题如何剪枝:
    优化搜索顺序:按照重量排序,优先选择较重的猫
    排除等效冗余:这道题搜索过程中已经没有枚举冗余情况,冗余是指先放这只还是那只,但这道题的搜索本来就是一只一只搜索
    可行性剪枝:当前猫放入超出最大承受重量,直接砍掉,这个可以用
    最优性剪枝:当前车的数量已经大于ans,砍掉直接退出
    记忆化搜索:不考虑
    综上所述,这道题可用优化搜索顺序,可行性剪枝,最优性剪枝
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 20;
    
    int n, m;
    int w[N];
    int sum[N];//每辆车放的小猫总重量
    int ans = N;//最坏情况下每只猫一辆车
    
    void dfs(int u, int k)
    {
        // 最优性剪枝,当前车的数量大于最优解,不会是答案,提前结束
        if (k >= ans) return;
        if (u == n)
        {
            ans = k;
            return;
        }
    
        for (int i = 0; i < k; i ++ )//枚举当前第u只猫可以放哪辆车上去
            if (sum[i] + w[u] <= m) // 可行性剪枝
            {
                sum[i] += w[u];
                dfs(u + 1, k);
                sum[i] -= w[u]; // 恢复现场
            }
    
        // 新开一辆车
        sum[k] = w[u];
        dfs(u + 1, k + 1);
        sum[k] = 0; // 恢复现场
    }
    
    int main()
    {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ ) cin >> w[i];
    
        // 优化搜索顺序
        sort(w, w + n);
        reverse(w, w + n);//最终要从大到小排序
    
        dfs(0, 0);//当前搜到第0只猫,当前车的数量是0
    
        cout << ans << endl;
    
        return 0;
    }
    

    AcWing 166. 数独

    /*
    先考虑搜索顺序,再考虑优化剪枝
    先随意选择一个空格子,枚举这个空格子可以填哪些数字,这里做个可行性剪枝,然后再随意选一个空格子
    剪枝(用了两个):
    优化搜索顺序:优先选择分支数较少的,也就是这个格子可填的数较少的,可行方案最少的
    排除等效冗余:没有,这道题搜索顺序固定
    可行性剪枝:当前所填数字不能与行,列,九宫格有重复
    最优性剪枝:没有,因为题目本身找的就是可行解
    位运算优化:
    用三个九位二进制数分别表示一行,一列,九宫格的状态,哪些用了,哪些没用,并且都没有才能选(与运算求交集)
    lobit运算可以在O(1)时间复杂度内返回二进制最后一个1
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 9, M = 1 << N;//M:行,列,九宫格都是一个二进制数,二进制1表示能用
    
    int ones[M], map[M];//两个数组做优化:一个是快速求出来一个状态有多少个1,一个用于lowbit
    int row[N], col[N], cell[3][3];
    char str[100];
    
    void init()
    {
        for (int i = 0; i < N; i ++ )
            row[i] = col[i] = (1 << N) - 1;//最开始每个格子都可以填,都为1
    
        for (int i = 0; i < 3; i ++ )
            for (int j = 0; j < 3; j ++ )
                cell[i][j] = (1 << N) - 1;
    }
    
    void draw(int x, int y, int t, bool is_set)
    {//辅助函数,在(x,y)这个位置上填一个数字t,布尔值表示在当前位置填一个数(dfs)还是删掉(恢复现场)
        if (is_set) str[x * N + y] = '1' + t;
        else str[x * N + y] = '.';
    
        int v = 1 << t;
        if (!is_set) v = -v;
    
        row[x] -= v;
        col[y] -= v;
        cell[x / 3][y / 3] -= v;
    }
    
    int lowbit(int x)
    {
        return x & -x;
    }
    
    int get(int x, int y)
    {
        return row[x] & col[y] & cell[x / 3][y / 3];
    }
    
    bool dfs(int cnt)
    {
        if (!cnt) return true;
    
        int minv = 10;//先找一个分支数量最少的空格,最多只有九种选择,取10
        int x, y;
        for (int i = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++ )
                if (str[i * N + j] == '.')
                {
                    int state = get(i, j);
                    if (ones[state] < minv)
                    {
                        minv = ones[state];
                        x = i, y = j;
                    }
                }
    
        int state = get(x, y);//枚举当前状态所有的1
        for (int i = state; i; i -= lowbit(i))
        {//二进制中比如第0到8位中,第3位为1代表4没填,可以填填看
            int t = map[lowbit(i)];
            draw(x, y, t, true);
            if (dfs(cnt - 1)) return true;
            draw(x, y, t, false);
        }
    
        return false;
    }
    
    int main()
    {
        for (int i = 0; i < N; i ++ ) map[1 << i] = i;//map就是log2
        for (int i = 0; i < 1 << N; i ++ )
            for (int j = 0; j < N; j ++ )
                ones[i] += i >> j & 1;//枚举每个二进制有多少个1
    
        while (cin >> str, str[0] != 'e')
        {
            init();//预处理行,列,九宫格
    
            int cnt = 0;//表示有多少个空格
            for (int i = 0, k = 0; i < N; i ++ )
                for (int j = 0; j < N; j ++, k ++ )
                    if (str[k] != '.')
                    {
                        int t = str[k] - '1';
                        draw(i, j, t, true);
                    }
                    else cnt ++ ;
    
            dfs(cnt);
    
            puts(str);
        }
    
        return 0;
    }
    

    AcWing 167. 木棒

    /*
    问题是给定n个数,把n个数分为若干组使每组总和相等,最多分为多少组
    木棒:表示每组总和  木棍表示切好的
    搜索顺序:先从小到大枚举木棒长度,对于固定长度依次从前往后拼接每根木棒
    剪枝:
    长度一定能整除所有木棒的和sum,只枚举sum的约数
    优化搜索顺序:从大到小枚举
    排除等效冗余:
    1.枚举的是组合数,而不是排列数,顺序无所谓,下标从小到大,拼接一根木棒时内部传一个参数表示下一根木棍从哪儿开始枚举
    2.如果当前木棍加到当前木棒中失败,则直接略过后面所有长度相等的木棍
    3.如果木棒的第一根木棍放置失败,则当前方案一定失败
    4.如果木棒的最后一根木棍放置失败,则当前方案一定失败
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 70;
    
    int n;
    int w[N];
    int sum, length;//所有木棍总和,枚举的每根木棒长度
    bool st[N];//每根小棍是否被用过
    
    bool dfs(int u, int cur, int start)
    {//当前枚举到第几根大棍,当前大棍的长度,小棍开始的位置
        if (u * length == sum) return true;//枚举是从第0根大棍枚举到第u-1根大棍
        if (cur == length) return dfs(u + 1, 0, 0);//第u根大棍拼接好了,开新棍
    
        for (int i = start; i < n; i ++ )
        {//当前大棍里枚举每一根小棍
            if (st[i] || cur + w[i] > length) continue;//可行性剪枝
    
            st[i] = true;
            if (dfs(u, cur + w[i], i + 1)) return true;
            st[i] = false;//恢复现场
    
            if (!cur || cur + w[i] == length) return false;//如果没有成功的小棍是第一根或最后一根
    
            int j = i;//排除与这根失败的小棍相邻的,长度相等的小棍
            while (j < n && w[j] == w[i]) j ++ ;
            i = j - 1;
        }
    
        return false;
    }
    
    int main()
    {
        while (cin >> n, n)
        {
            memset(st, 0, sizeof st);
            sum = 0;
    
            for (int i = 0; i < n; i ++ )
            {
                cin >> w[i];
                sum += w[i];
            }
    
            sort(w, w + n);
            reverse(w, w + n);//小棍从大到小放置
    
            length = 1;
            while (true)
            {//从小到大枚举每根大棍长度
                if (sum % length == 0 && dfs(0, 0, 0))//从前往后枚举每根大棍,当前大棍是0,当前从0开始枚举
                {
                    cout << length << endl;
                    break;
                }
                length ++ ;
            }
        }
    
        return 0;
    }
    

    AcWing 168. 生日蛋糕

    /*
    从下往上看,每层高度,半径严格递减
    
    搜索顺序:
    自底向上搜,给之后搜索留的余地越来越少越好,每一层从大到小先枚举最底层半径再枚举高度(因为在总面积中,半径是^2级别)
    
    可行性剪枝:(枚举的r,h有范围)
    当前枚举第u层,u<=r(u)<=min( r(u+1)-1 , sqrt(n-v) )  ,   u<=h(u)<=min( h(u+1)-1 , (n-v)/(r(u)^2)  )
    v是下面层数的总体积,n是给定总体积,n-v>= r(u)^2 *h(u)
    
    预处理前u层体积与表面积最小值,第一层半径与高取1,第二层半径与高取2,要保证
    v+min(u)<=n(可行性剪枝)  s+min(u)<ans(ans是当前记录的合法方案)(最有效剪枝)如果取到=说明当前解不能优化最优解,没必要继续搜索
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int N = 25, INF = 1e9;
    
    int n, m;
    int minv[N], mins[N];
    int R[N], H[N];
    int ans = INF;
    
    void dfs(int u, int v, int s)
    {
        if (v + minv[u] > n) return;
        if (s + mins[u] >= ans) return;
        if (s + 2 * (n - v) / R[u + 1] >= ans) return;
    
        if (!u)
        {
            if (v == n) ans = s;
            return;
        }
    
        for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r -- )
            for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h -- )
            {
                int t = 0;
                if (u == m) t = r * r;
                R[u] = r, H[u] = h;
                dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
            }
    }
    
    int main()
    {
        cin >> n >> m;
    
        for (int i = 1; i <= m; i ++ )
        {
            minv[i] = minv[i - 1] + i * i * i;
            mins[i] = mins[i - 1] + 2 * i * i;
        }
    
        R[m + 1] = H[m + 1] = INF;
    
        dfs(m, 0, 0);
    
        if (ans == INF) ans = 0;
        cout << ans << endl;
    
        return 0;
    }
    

    迭代加深

    AcWing 170. 加成序列

    /*
    迭代加深:在搜索时,搜索树可能比较深,答案在比较浅的层中,搜索浪费很多时间,迭代加深就是针对这个情况
    与宽搜类似,但会定义一个层数上限,逐步扩大范围,宽搜时间复杂度是指数级别,每次会把上一层时间节点全部记录下来
    迭代加深本质还是DFS,每次会记录一条路径上的信息,它的时间复杂度是O(n),与高度成正比
    DFS加剪枝后很难去算具体的时间复杂度,粗略估计即可
    
    这道题最坏情况下搜索树深度为100层,但是答案深度估计不大
    
    剪枝:
    优化搜索顺序:优先枚举较大的数会更快的涨到n
    排除等效冗余:
    比如1+4或2+3求和结果相同,没必要重复枚举,可以在每一个节点里面开一个布尔数组,判断每个数是否之前被枚举过
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 110;
    
    int n;
    int path[N];
    
    bool dfs(int u, int k)//当前层数,最大层数
    {
        if (u == k) return path[u - 1] == n;
    
        bool st[N] = {0};//定义布尔数组,排除等效冗余
        for (int i = u - 1; i >= 0; i -- )//从大到小枚举当前所有分支
            for (int j = i; j >= 0; j -- )
            {
                int s = path[i] + path[j];//s是这一层可能会放的数,它是前任意两层的数之和
                if (s > n || s <= path[u - 1] || st[s]) continue;
                st[s] = true;//这两层循环是在枚举这一层尝试放哪些数
                path[u] = s;//这里没有必要恢复现场,因为会被重复赋值
                if (dfs(u + 1, k)) return true;
            }
    
        return false;
    }
    
    int main()
    {
        path[0] = 1;
        while (cin >> n, n)//多组测试数据,直到读到0为止
        {
            int k = 1;//从小到大枚举迭代加深的范围
            while (!dfs(1, k)) k ++ ;//1表示当前层数为第一层
    
            for (int i = 0; i < k; i ++ ) cout << path[i] << ' ';
            cout << endl;
        }
    
        return 0;
    }
    

    双向DFS

    AcWing 171. 送礼物

    /*
    双向DFS和双向BFS原理一样
    这道题看着很像背包问题,但注意数据范围,背包问题一定会超时,所以不能DP,但是由于n比较小,所以尝试暴搜
    问题是所有总重量不超过w的选法里面,重量最大值是多少,所以只需要想要个方法枚举所有方案,取最大值
    暴力搜索是依次枚举每件物品选与不选 2^n(这里n最多为46,必然超时)
    双向DFS,从两个方向来搜
    空间换时间 把n个物品看成一个区间,先暴力搜索遍历由前一半物品能凑出来的所有重量的集合,n最多为46
    所有前一半可以凑出来最多2^23种不同情况(这里可以加个小优化,排序判重)
    然后再枚举后一半每种物品的选择,也是有2^23种不同情况,对于每种情况,比如当前重量为s,我们需要在前面一半得到的情况中
    找到小于等于(w-s)的最大值(二分) 
    拆分一下,先把前一半算出来,再暴力搜索最后一半,然后查表,不需要重新暴力搜索
    时间复杂度:2^(K)+2^(N-K)*K 这里不一定非要取一半,比如可以取k=25尽可能是总和最小
    
    优化:
    搜索顺序:从大到小排序搜索,优先搜索较大的数,更加接近上限,层数很短,节点更少,这样也可以更快进行可行性剪枝
    
    总结:
    1.将所有物品按照重量从大到小排序
    2.先将前k件物品能凑出的所有重量打表,然后排序判重
    3.搜索剩下的N-K件物品的选择方式,然后在表中二分出不超过w的最大值
    */
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 46;
    
    int n, m, k;
    int w[N];//存储每件物品的重量
    int weights[1 << 25], cnt = 1;
    //k最大是25,是要存2^25个数,cnt从1开始是因为0也是一个可以枚举的重量,cnt表示当前正在枚举哪个数
    int ans;
    
    void dfs1(int u, int s)//当前枚举到哪个数,第二项是当前的和
    {
        if (u == k)
        {
            weights[cnt ++ ] = s;
            return;
        }
    
        dfs1(u + 1, s);//当前不选这个物品
        if ((LL)s + w[u] <= m) dfs1(u + 1, s + w[u]);//如果可以选的话,选
    }
    
    void dfs2(int u, int s)
    {
        if (u == n)
        {//如果某种选择方案已经枚举到了第n个数
            int l = 0, r = cnt - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if ((LL)s + weights[mid] <= m) l = mid;
                else r = mid - 1;
            }
            ans = max(ans, s + weights[l]);
            return;
        }
    
        dfs2(u + 1, s);//不选
        if ((LL)s + w[u] <= m) dfs2(u + 1, s + w[u]);//选
    }
    
    int main()
    {
        cin >> m >> n;
        for (int i = 0; i < n; i ++ ) cin >> w[i];
    
        sort(w, w + n);
        reverse(w, w + n);//优化搜索顺序,从大到小排序
    
        k = n / 2 + 2;//前k件物品打表,这个是有所给数据范围估计来的,后半段有个二分,平衡两端计算量
        dfs1(0, 0);
    
        sort(weights, weights + cnt);//排序
        cnt = unique(weights, weights + cnt) - weights;//判重,删掉数组中重复元素,返回值是剩下不同元素个数
    
        dfs2(k, 0);//dfs后半段,从k开始,当前和是0
    
        cout << ans << endl;
    
        return 0;
    }
    

    IDA*

    AcWing 180. 排书

    
    

    AcWing 181. 回转游戏

    
    
    展开全文
  • 目录背包模型一、01背包AcWing 423. 采药二、完全背包三、多重背包四、分组背包 背包模型 一、01背包 AcWing 423. 采药 板子 #include <bits/stdc++.h> #define endl '\n' #define IOS ios::sync_with_stdio...

    目录

    数字三角形模型(只能向右和向下或向左和向上)

    AcWing 1015. 摘花生

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 110;
    
    int f[N][N];
    int g[N][N];
    
    int main()
    {
        int _; cin >> _;
        
        while (_ -- )
        {
            int r, c;
            cin >> r >> c;
            for (int i = 1; i <= r; i ++ )
                for (int j = 1; j <= c; j ++ )
                    cin >> g[i][j];
            
            for (int i = 1; i <= r; i ++ )
                for (int j = 1; j <= c; j ++ )
                {
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j];
                }
            
            cout << f[r][c] << endl;
        }
        return 0;
    }
    
    

    AcWing 1018. 最低通行费(曼哈顿距离-向右和向下-求最小值-初始化)

    在这里插入图片描述

    • 四相邻,因此在矩阵中找任意两点的距离,用的不是欧氏距离 d = x 1 − x 2 2 + y 1 − y 2 2 d=\sqrt{{x1-x2}^2+{y1-y2}^2} d=x1x22+y1y22 ,而是曼哈顿距离 d = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ d=|x1-x2|+|y1-y2| d=x1x2+y1y2。从 ( 1 , 1 ) (1,1) (1,1) ( n , n ) (n,n) (n,n)的曼哈顿距离是 2 n − 2 2n-2 2n2,而题目要求 2 n − 1 2n-1 2n1时间内,因此,每次移动只能向右或向下,那么就是经典数字三角形。
    • 由于求最小值,需要将所有状态初始化为正无穷(这样就无法使用这些状态了),初始化状态的起点,以及状态转移越界判断。刚才那题(求最大值)就不用。
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 110, INF = 1e9;
    
    int w[N][N], f[N][N];
    
    int main()
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                cin >> w[i][j];
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
            {
                if (i == 1 && j == 1) f[i][j] = w[i][j];        // 初始化起点
                else
                {
                    f[i][j] = INF;      // 初始化
                    if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);       // 不是第一行才能从上边走来
                    if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);       // 不是第一列才能从左边走来
                }
            }
        
        cout << f[n][n] << endl;
        return 0;
    }
    
    
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 110;
    
    int w[N][N], f[N][N];
    
    int main()
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                cin >> w[i][j];
        
        memset(f, 0x3f, sizeof f);
        f[1][1] = w[1][1];
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
            {
                f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
                f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
            }
        
        cout << f[n][n] << endl;
        
        return 0;
    }
    
    

    AcWing 1027. 方格取数

    在这里插入图片描述

    在这里插入图片描述

    • 只走一次时(摘花生): f [ i ] [ j ] f[i][j] f[i][j]表示所有从 ( 1 , 1 ) (1,1) (1,1)走到 ( i , j ) (i,j) (i,j)的路径的最大值, f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] + w [ i ] [ j ] , f [ i ] [ j − 1 ] + w [ i ] [ j ] ) f[i][j]=max(f[i-1][j]+w[i][j],f[i][j-1]+w[i][j]) f[i][j]=max(f[i1][j]+w[i][j],f[i][j1]+w[i][j])
    • 走两次时 :让两人同时走,题目条件转化为两条路径重合部分的值只能取一次 f [ i 1 , j 1 , i 2 , j 2 ] f[i1,j1,i2,j2] f[i1,j1,i2,j2]表示所有从 ( 1 , 1 ) , ( 1 , 1 ) (1,1),(1,1) (1,1),(1,1)分别走到 ( i 1 , j 1 ) , ( i 2 , j 2 ) (i1,j1),(i2,j2) (i1,j1),(i2,j2)的所有路径的最大值,那么只有在 i 1 + j 1 = = i 2 + j 2 i1+j1 == i2+j2 i1+j1==i2+j2时,两条路径的格子才可能重合。(其实就是同时走,所以步数是一样的,那么就可以从四维优化成三维了)
    • k k k表示两条路线当前走到的格子的横纵坐标之和, f [ k , i 1 , i 2 ] f[k,i_1,i_2] f[k,i1,i2]表示所有从 ( 1 , 1 ) , ( 1 , 1 ) (1,1),(1,1) (1,1),(1,1)分别走到 ( i 1 , k − i 1 ) , ( i 2 , k − i 2 ) (i_1,k-i_1),(i_2,k-i_2) (i1,ki1),(i2,ki2)的路径的最大值。 k k k相当于就是阶段。
    • f [ k , i 1 , i 2 ] f[k,i_1,i_2] f[k,i1,i2]按照最后一步时两条路线分别怎么走划分成四类
    • “第一条下,第二条下” :两条路线都分别两部来求。第一条路线中从 ( 1 , 1 ) (1,1) (1,1)走到 ( i 1 − 1 , k − i 1 ) (i_1-1,k-i_1) (i11,ki1)有多条路径,而最后一步从 ( i 1 − 1. k − i 1 ) (i_1-1.k-i_1) (i11.ki1)走到 ( i 1 , k − i 1 ) (i_1,k-i_1) (i1,ki1)只有一条路径,要求最大值的话,先求前面的最大值,再加上最后一步的值,前面这个最大值恰好就是状态 f ( k − 1 , i 1 − 1 , i 2 − 1 ) f(k-1,i_1-1,i_2-1) f(k1,i11,i21),后面一步要判断一下 ( i 1 − 1 , k − i 1 ) , ( i 2 − 1 , k − i 2 ) (i_1-1,k-i_1),(i_2-1,k-i_2) (i11,ki1),(i21,ki2)是不是同一个格子,如果是同一格子…
    • 同理,后三类也会有个最大值,最后总的最大值是这四个取个max
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 15;
    
    int w[N][N];
    int f[N * 2][N][N];
    
    int main()
    {
        int n;
        cin >> n;
        
        int a, b, c;
        while (cin >> a >> b >> c, a || b || c) w[a][b] = c;
        
        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)
                    {
                        int t = w[i1][j1];
                        if (i1 != i2) t += w[i2][j2];
                        int &x = f[k][i1][i2];
                        x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
                        x = max(x, f[k - 1][i1 - 1][i2] + t);
                        x = max(x, f[k - 1][i1][i2] + t);
                        x = max(x, f[k - 1][i1][i2 - 1] + t);
                    }
                }
        
        cout << f[2 * n][n][n] << endl;
        
        return 0;
    }
    
    

    AcWing 275. 传纸条

    在这里插入图片描述

    • 从右下角走到左上角就等价于从左上角走到右下角。那么同上题,仅有细节改动(这里两个人不能走相同格子,注意除了起点和终点)。

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 55;
    
    int w[N][N];
    int f[N * 2][N][N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                cin >> w[i][j];
        
        for (int k = 2; k <= n + m; k ++ )
            for (int i = max(1, k - m); i <= n && i < k; i ++ )
                for (int j = max(1, k - m); j <= n && j < k; j ++ )
                {
                    int t = w[i][k - i];
                    if (i != j || k == 2 || k == n + m)
                    {
                        t += w[j][k - j];
                        for (int a = -1; a <= 0; a ++ )
                            for (int b = -1; b <= 0; b ++ )
                            {
                                f[k][i][j] = max(f[k][i][j], f[k - 1][i + a][j + b] + t);
                            }
                    }
                }
        
        cout << f[n + m][n][n] << endl;
        
        return 0;
    }
    
    

    最长上升子序列模型

    AcWing 1017. 怪盗基德的滑翔翼

    在这里插入图片描述

    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 110;
    
    int n;
    int h[N];
    int f[N];
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T -- )
        {
            scanf("%d", &n);
            for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]);
    
            int res = 0;
            for (int i = 0; i < n; i ++ )
            {
                f[i] = 1;
                for (int j = 0; j < i; j ++ )
                    if (h[i] < h[j])
                        f[i] = max(f[i], f[j] + 1);
                res = max(res, f[i]);
            }
    
            memset(f, 0, sizeof f);
            for (int i = n - 1; i >= 0; i -- )
            {
                f[i] = 1;
                for (int j = n - 1; j > i; j -- )
                    if (h[i] < h[j])
                        f[i] = max(f[i], f[j] + 1);
                res = max(res, f[i]);
            }
    
            printf("%d\n", res);
        }
    
        return 0;
    }
    
    

    AcWing 1014. 登山

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010;
    
    int n;
    int h[N];
    int f[N], g[N];
    
    int main()
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]);
    
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1;
            for (int j = 0; j < i; j ++ )
                if (h[i] > h[j])
                    f[i] = max(f[i], f[j] + 1);
        }
    
        for (int i = n - 1; i >= 0; i -- )
        {
            g[i] = 1;
            for (int j = n - 1; j > i; j -- )
                if (h[i] > h[j])
                    g[i] = max(g[i], g[j] + 1);
        }
    
        int res = 0;
        for (int i = 0; i < n; i ++ ) res = max(res, f[i] + g[i] - 1);
    
        printf("%d\n", res);
    
        return 0;
    }
    
    

    AcWing 482. 合唱队形

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010;
    
    int n;
    int h[N];
    int f[N], g[N];
    
    int main()
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]);
    
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1;
            for (int j = 0; j < i; j ++ )
                if (h[i] > h[j])
                    f[i] = max(f[i], f[j] + 1);
        }
    
        for (int i = n - 1; i >= 0; i -- )
        {
            g[i] = 1;
            for (int j = n - 1; j > i; j -- )
                if (h[i] > h[j])
                    g[i] = max(g[i], g[j] + 1);
        }
    
        int res = 0;
        for (int i = 0; i < n; i ++ ) res = max(res, f[i] + g[i] - 1);
    
        printf("%d\n", n - res);
    
        return 0;
    }
    
    
    

    AcWing 1012. 友好城市

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 5010;
    
    int n;
    PII city[N];
    int f[N];
    
    int main()
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d%d", &city[i].first, &city[i].second);
        sort(city, city + n);
    
        int res = 0;
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1;
            for (int j = 0; j < i; j ++ )
                if (city[i].second > city[j].second)
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
    
        printf("%d\n", res);
    
        return 0;
    }
    
    

    AcWing 1016. 最大上升子序列和

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 1010;
    
    int w[N], f[N];
    
    int main()
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> w[i];
        
        int res = 0;
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = w[i];
            for (int j = 1; j < i; j ++ )
                if (w[i] > w[j])
                    f[i] = max(f[i], f[j] + w[i]);
            res = max(res, f[i]);
        }
        
        cout << res << endl;
        
        return 0;
    }
    
    

    AcWing 1010. 拦截导弹(贪心+stringstream语法)

    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    • q数组存每个子序列结尾的数。每次放进一个数都去找结尾大于等于它的最小的数,会发现,这样的话,q数组是单调递增的
      在这里插入图片描述
    • 且发现与前面最长上升子序列问题的贪心解法一致,因此最长上升子序列的方案数等于用最少非上升子序列覆盖整个序列的方案数。
    • 不过这道题的时间复杂度卡在LIS( O ( n 2 ) O(n^2) O(n2)),因此用了二分复杂度还是这样高,没有实际意义,就不写二分了。
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #include <sstream>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 1010;
    
    int n;
    int w[N], f[N], q[N];		// q数组记录每个子序列末尾的值
    
    int main()
    {
        string line;
        getline(cin, line);
        stringstream sin(line);        // #include <sstream>!!
        while (sin >> w[n]) n ++ ;
        // while (cin >> w[n]) n ++ ;
        
        
        int res = 0, cnt = 0;
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1;
            for (int j = 0; j < i; j ++ )
                if (w[i] <= w[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
            
            // 在单调递增的序列中找大于等于w[i]的最小的数
            int k = 0;
            while (k < cnt && q[k] < w[i]) k ++ ;		// 下标合法 && 找大于等于w[i]的数 
            if (k == cnt) q[cnt ++ ] = w[i];		// 下标不合法
            else q[k] = w[i];
        }
        
        cout << res << endl << cnt << endl;
        
        return 0;
    }
    
    

    AcWing 187. 导弹防御系统(dfs求最小步数)

    在这里插入图片描述
    在这里插入图片描述

    • 这题相对上题有两种选择了,就是在上一题框架之外套一层爆搜,那么爆搜需要的空间大约是 2 n 2^n 2n
    • dfs求最小步数有两种方法 :1.记一个全局最小值。2.迭代加深。这题两种都可以。此处用第一种。
    • 为什么很多题不用bfs来求解呢 ?因为bfs需要的空间太大,会把每一层都存下来,每一层有指数级别空间,而dfs只存一个路径,是线性路径。且bfs不太好剪枝,dfs是搜索树,搜的时候如果发现它的分支不太好就直接叉掉了一整棵树。这道题状态也不好用bfs。
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #include <sstream>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 55;
    
    int n;
    int q[N];
    int up[N], down[N];
    int ans;
    
    void dfs(int u, int su, int sd)
    {
        if (su + sd >= ans) return ;
        if (u == n)
        {
            ans = su + sd;
            return ;
        }
        
        // 情况1:将当前数放入上升子序列
        int k = 0;
        while (k < su && up[k] >= q[u]) k ++ ;
        int t = up[k];
        up[k] = q[u];
        if (k >= su) dfs(u + 1, su + 1, sd);
        else dfs(u + 1, su, sd);
        up[k] = t;      // 回溯
        
        // 情况2:将当前数放入下降子序列
        k = 0;
        while (k < sd && down[k] <= q[u]) k ++ ;
        t = down[k];
        down[k] = q[u];
        if (k >= sd) dfs(u + 1, su, sd + 1);
        else dfs(u + 1, su, sd);
        down[k] = t;
    }
    
    int main()
    {
        while (cin >> n, n)
        {
            for (int i = 0; i < n; i ++ ) cin >> q[i];
            
            ans = n;        // 注意初始化!!
            dfs(0, 0, 0);
            
            cout << ans << endl;
        }
    }
    
    

    AcWing 272. 最长公共上升子序列

    在这里插入图片描述
    在这里插入图片描述

    • f [ i , j ] f[i,j] f[i,j]表示所有在 A [ 1 , i ] , B [ 1 , j ] A[1,i],B[1,j] A[1,i],B[1,j]中都出现过,且以 B [ j ] B[j] B[j]结尾的所有公共上升子序列的集合,属性是 m a x max max
    • 按照 A [ i ] A[i] A[i]是否包含在公共子序列中分为两个集合,“不包含”的集合显然为 f [ i − 1 , j ] f[i-1,j] f[i1,j](所有在 A [ i − 1 ] , B [ j ] A[i-1],B[j] A[i1],B[j]中出现,且以 B [ j ] B[j] B[j]结尾的所有…),“包含”则分为这个公共子序列中倒数第二个是什么,分成若干类 :第一类:不存在倒数第二个数,即公共上升子序列长度是1;第二类 :倒数第二个数是 B [ 1 ] B[1] B[1];第三类 :倒数第二个数是 B [ 2 ] B[2] B[2];…;倒数第二个数是 B [ j − 1 ] B[j-1] B[j1]。即一共j种可能,分为j个子集,要想求右边这个的最大值就是求这j个子集的 m a x max max
    • 但这样的朴素做法是 O ( N 3 ) O(N^3) O(N3),无法通过。dp的优化需要根据代码等价变形,因此我们先写出朴素写法。
    // TLE
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #include <sstream>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 3e3 + 10;
    
    int a[N], b[N];
    int f[N][N];
    
    int main()
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        for (int i = 1; i <= n; i ++ ) cin >> b[i];
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
            {
                f[i][j] = f[i - 1][j];
                if (a[i] == b[j])
                {
                    int maxv = 1;
                    for (int k = 1; k < j; k ++ )
                        if (b[k] < b[j])
                            maxv = max(maxv, f[i - 1][k] + 1);
                    f[i][j] = max(f[i][j], maxv);
                }
            }
        
        int res = 0;
        for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
        
        cout << res << endl;
        return 0;
    }
    
    

    在这里插入图片描述

    • 优化 :b[j] == a[i],因此转化为a[i],这个循环就是求在b[1]…b[j-1]中所有小于a[i]的元素中,它所对应的f[i-1,k]的最大值再加1。这样的话,在求b[j+1]时会再把前面这个循环循环一遍,重新看一遍对应的f的最大值
    • 因此我们用maxv直接存前缀中打对勾的所对应的最大值即可,在求b[j+1]时就不需要重新枚举了,直接判断b[j+1]即可
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #include <sstream>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 3e3 + 10;
    
    int a[N], b[N];
    int f[N][N];
    
    int main()
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        for (int i = 1; i <= n; i ++ ) cin >> b[i];
        
        for (int i = 1; i <= n; i ++ )
        {
            int maxv = 1;
            for (int j = 1; j <= n; j ++ )
            {
                f[i][j] = f[i - 1][j];
                if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
                if (b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);		// 只有在b[j]<a[i]的情况下才会被打对勾,才可能用对应的f更新maxv
            }
        }
        
        int res = 0;
        for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
        
        cout << res << endl;
        return 0;
    }
    
    

    背包模型

    背包问题初始化总结

    在这里插入图片描述
    总的来说就是 :求方案数, f [ 0 ] = 1 f[0]=1 f[0]=1;求最大/最小值 : f [ 0 ] = 0 f[0]=0 f[0]=0

    一、01背包

    AcWing 423. 采药

    在这里插入图片描述
    板子

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 1010;
    
    int f[N];
    
    int main()
    {
        int n, m;
        cin >> m >> n;
        
        for (int i = 0; i < n; i ++ )
        {
            int v, w;
            cin >> v >> w;
            for (int j = m; j >= v; j -- )
                f[j] = max(f[j], f[j - v] + w);
        }
        
        cout << f[m] << endl;
        
        return 0;
    }
    
    

    AcWing 1024. 装箱问题

    在这里插入图片描述
    价值和体积是同一个变量。注意题目所求为剩余。

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 2e4 + 10;
    
    int f[N];
    
    int main()
    {
        int n, m;
        cin >> m >> n;
        for (int i = 0; i < n; i ++ )
        {
            int v;
            cin >> v;
            for (int j = m; j >= v; j -- )
                f[j] = max(f[j], f[j - v] + v);
        }
        
        cout << m - f[m] << endl;
        
        return 0;
    }
    
    

    AcWing 1022. 宠物小精灵之收服(二维体积)

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 1010;
    
    int f[N][N];
    
    int main()
    {
        int V1, V2, n;
        cin >> V1 >> V2 >> n;
        for (int i = 0; i < n; i ++ )
        {
            int v1, v2;
            cin >> v1 >> v2;
            for (int j = V1; j >= v1; j -- )
                for (int k = V2 - 1; k >= v2; k -- )
                    f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
        }
        
        cout << f[V1][V2 - 1] << " ";
        for (int i = 0; i < V2; i ++ )
            if (f[V1][V2 - 1] == f[V1][i])
            {
                cout << V2 - i << endl;
                break;
            }
        
        return 0;
    }
    
    

    AcWing 278. 数字组合(体积恰好,求总方案数)

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 1e4 + 10;
    
    int f[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        
        f[0] = 1;
        
        for (int i = 0; i < n; i ++ )
        {
            int v;
            cin >> v;
            for (int j = m; j >= v; j -- )
                f[j] += f[j - v];
        }
        
        cout << f[m] << endl;
        
        return 0;
    }
    
    

    AcWing 8. 二维费用的背包问题(二维体积)

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 110;
    
    int f[N][N];
    
    int main()
    {
        int n, V1, V2;
        cin >> n >> V1 >> V2;
        for (int i = 0; i < n; i ++ )
        {
            int v1, v2, w;
            cin >> v1 >> v2 >> w;
            for (int j = V1; j >= v1; j -- )
                for (int k = V2; k >= v2; k -- )
                    f[j][k] = max(f[j][k], f[j - v1][k - v2] + w);
        }
        
        cout << f[V1][V2] << endl;
        return 0;
    }
    
    

    AcWing 1020. 潜水员(二维体积,体积至少,最小价值)

    在这里插入图片描述

    注意状态转移时体积为负数也是合法的。

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 85;
    
    int f[N][N];
    
    int main()
    {
        int V1, V2, n;
        cin >> V1 >> V2 >> n;
        
        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;
        
        for (int i = 0; i < n; i ++ )
        {
            int v1, v2, w;
            cin >> v1 >> v2 >> w;
            for (int j = V1; j >= 0; j -- )
                for (int k = V2; k >= 0; k -- )
                    f[j][k] = min(f[j][k], f[max(0, j - v1)][max(0, k - v2)] + w);
        }
        
        cout << f[V1][V2] << endl;
    }
    
    

    AcWing 426. 开心的金明

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 3e4 + 10;
    
    int f[N];
    
    int main()
    {
        int n, m;
        cin >> m >> n;
        for (int i = 0; i < n; i ++ )
        {
            int v, p;
            cin >> v >> p;
            p *= v;
            for (int j = m; j >= v; j -- )
                f[j] = max(f[j], f[j - v] + p);
        }
        cout << f[m] << endl;
        return 0;
    }
    
    

    AcWing 11. 背包问题求方案数(求最优选法的方案数)

    在这里插入图片描述

    • g [ i ] [ j ] g[i][j] g[i][j]表示 f [ i ] [ j ] f[i][j] f[i][j]取最大值的方案数
    • 由于在讨论 f [ i ] [ j ] f[i][j] f[i][j] m a x max max时会将这个集合划分成两半,即不选 i i i更新为 f [ i − 1 ] [ j ] f[i-1][j] f[i1][j],选 i i i更新为 f [ i − 1 ] [ j − v [ i ] ] + w [ i ] f[i-1][j-v[i]]+w[i] f[i1][jv[i]]+w[i]
    • 如果不选 i i i更大, g [ i ] [ j ] g[i][j] g[i][j]更新为 g [ i − 1 ] [ j ] g[i-1][j] g[i1][j],选 i i i更大则更新为 g [ i − 1 ] [ j − v [ i ] ] g[i-1][j-v[i]] g[i1][jv[i]],如果相等则更新为 g [ i − 1 ] [ j ] + g [ i − 1 ] [ j − v [ i ] ] g[i-1][j]+g[i-1][j-v[i]] g[i1][j]+g[i1][jv[i]]
    • g [ i ] [ j ] g[i][j] g[i][j]的优化 :这里第 i i i层也只和第 i − 1 i-1 i1层有关系,且j也只和更小的j有关系,所以g也可以优化成一维,所以这道题可以用一维写。
    • 注意这里 f [ i ] [ j ] f[i][j] f[i][j]需要存储为“体积恰好为j“而非至多是j,否则涉及容斥定理。
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    
    const int N = 1e3 + 10, mod = 1e9 + 7;
    
    int f[N], g[N];
             
    int main()
    {
        memset(f, -0x3f, sizeof f);
        
        f[0] = 0;
        g[0] = 1;
        
        int n, m;
        scanf("%d%d", &n, &m);
        
        for (int i = 1; i <= n; i ++ )
        {
            int v, w;
            scanf("%d%d", &v, &w);
            for (int j = m; j >= v; j -- )
            {
              	// 两个if而不是else if
                int cnt = 0;
                int maxv = max(f[j], f[j - v] + w);
                if (f[j] == maxv) cnt += g[j];
                if (f[j - v] + w == maxv) cnt += g[j - v];
                g[j] = cnt % mod;
                f[j] = maxv;
            }
        }
        
        int res = 0, cnt = 0;
      	// 题目所求为“体积最多为”,这里状态表示的是“体积恰好为”,所以价值最大的并不一定是体积最大的
        for (int i = 1; i <= m; i ++ ) res = max(res, f[i]);
        
        for (int i = 1; i <= m; i ++ )
            if (f[i] == res)
                cnt = (cnt + g[i]) % mod;
        
        printf("%d\n", cnt);
                     
        return 0;
    }
    
    
    

    AcWing 12. 背包问题求具体方案(打印方案)

    在这里插入图片描述

    • 由于求字典序最小 :能选第一个物品就必须选第一个,能选第二个就必须选第二个…即前面的物品能选则选,所有在更新时左右两个集合都可以选时,优先选择右边 f [ i − 1 ] [ j − v [ i ] ] + w [ i ] f[i-1][j-v[i]]+w[i] f[i1][jv[i]]+w[i]的集合;如果右边可以选左边不可,必然选右边;如果左边可以右边不可以,就不能取第 i i i个物品。
    • dp时需要从后往前推,那么在求方案时就可以从前往后了,通过判断 f [ i ] [ j ] f[i][j] f[i][j]的值等于左边还是右边来判断第 i i i个物品又没有选择。
    • 求方案时就不能压缩空间了,由于不压缩空间,体积从小到大循环和从大到小循环都一样。
    • 由于从后往前推, f [ i ] [ j ] f[i][j] f[i][j]是从 i + 1 i+1 i+1更新的。
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 1010;
    
    int f[N][N];
    int v[N], w[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
        
        for (int i = n; i; i -- )
            for (int j = 0; j <= m; j ++ )
            {
                f[i][j] = f[i + 1][j];
                if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
            }
        
        int j = m;
        for (int i = 1; i <= n; i ++ )
            if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
            {
                cout << i << " ";
                j -= v[i];
            }
        return 0;
    }
    
    

    AcWing 734. 能量石 (贪心)

    在这里插入图片描述

    • 考虑任意两个(是从这个大的集合里任选的)相邻的能量石 i i i i + 1 i + 1 i+1,假设先吃 i i i再吃 i + 1 i + 1 i+1,且假定吃的时候两块能量石能量都大于0(其实一定满足,因为它在那个大的集合内,且那个大的集合不吃能量为0的),总共能获得的能量是 E i + E j − s i ∗ l i + 1 E_i + E_j - s_i * l_{i+1} Ei+Ejsili+1,反之就是 E i + E j − s i + 1 ∗ l i E_i + E_j - s_{i+1}*l_i Ei+Ejsi+1li。因此,只要有 s i ∗ l l + 1 < s i + 1 ∗ l i s_i*l_{l+1} < s_{i+1}*l_i sill+1<si+1li,就一定有先吃i再吃i+1更好,这个整理一下就是 s i l i < s i + 1 l i \frac{s_i}{l_i}<\frac{s_{i+1}}{l_i} lisi<lisi+1,因此将所有能量石按这个从小到大排序,一定是最优的。因此可以证明最优方案一定是在小圈(从从小到大排好序中选)里的,所以只要找小圈里的最优方案即可。
    • f [ i ] [ j ] f[i][j] f[i][j]表示只从前i块能量石中选,且总体积“恰好”是j的方案,属性是 m a x max max
    • 转移方程 f [ j ] = m a x ( f [ j ] , f [ j − s ] + e − ( j − s ) ∗ l ) f[j]=max(f[j],f[j-s]+e-(j-s)*l) f[j]=max(f[j],f[js]+e(js)l)
    • m是所有能量石时间(体积)之和。
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 1e4 + 10;     // N * S
    
    int f[N];
    
    struct Stone
    {
        int s, e, l;
        bool operator< (const Stone &W) const
        {
            return s * W.l < W.s * l;
        }
    }stone[N];
    
    int main()
    {
        int _; cin >> _;
        
        for (int C = 1; C <= _; C ++ )
        {
            int n;
            cin >> n;
            
            int m = 0;
            for (int i = 0; i < n; i ++ )
            {
                cin >> stone[i].s >> stone[i].e >> stone[i].l;
                m += stone[i].s;
            }
            
            sort(stone, stone + n);
            
            memset(f, -0x3f, sizeof f);
            f[0] = 0;
            
            for (int i = 0; i < n; i ++ )
            {
                int s = stone[i].s, e = stone[i].e, l = stone[i].l;
                for (int j = m; j >= s; j -- )
                    f[j] = max(f[j], f[j - s] + e - (j - s) * l);
            }
            
            int res = 0;
            for (int i = 0; i <= m; i ++ ) res = max(res, f[i]);
            cout << "Case #" << C << ": " << res << endl;
        }
    }
    
    
    

    二、完全背包

    AcWing 1023. 买书(体积恰好,求总方案数)

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 1010;
    
    int f[N];
    int v[] = {10, 20, 50, 100};
    
    int main()
    {
        int m;
        cin >> m;
        
        f[0] = 1;
        for (int i = 0; i < 4; i ++ )
            for (int j = v[i]; j <= m; j ++ )
                f[j] += f[j - v[i]];
        
        cout << f[m] << endl;
        
        return 0;
    }
    
    

    AcWing 1021. 货币系统(体积恰好,求总方案数)

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 3010;
    
    ll f[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        
        f[0] = 1;
        
        for (int i = 0; i < n; i ++ )
        {
            int v;
            cin >> v;
            for (int j = v; j <= m; j ++ )
                f[j] += f[j - v];
        }
        
        cout << f[m] << endl;
        
        return 0;
    }
    
    

    AcWing 532. 货币系统(体积恰好,求总方案数)

    在这里插入图片描述

    • 发现有三个性质 :1. a 1 a_1 a1, … , a n a_n an一定都能被表示出来。2.在最优解中, b i bi bi一定是从 a a a中选的。3. b 1 b1 b1 , … , b m b_m bm一定不能被其他 b i b_i bi表示出来。
    • 因此,从小到大排序,判断 a i a_i ai能否被若干个 a 1 a_1 a1,…, a i + 1 a_{i + 1} ai+1表示,如果能则说明 a i a_i ai是多余的,一定不选,否则一定选。
    • 问题转化为能否用无穷个体积为 a 1 a_1 a1, … a i − 1 a_{i-1} ai1的物品恰好装满容积为 a i a_i ai的背包,转化为完全背包问题判断方案数是否为0。

    在这里插入图片描述

    // 这是一道线性代数问题
    // 求解一个向量组的秩(最大无关向量组的向量个数)
    // 但代码写起来就是一个模拟筛的过程
    // 从小到大,首先查看当前数是否已经被筛掉
    // 1)如果没有就将它加入到最大无关向量组中,并把它以及它和此前的硬币的线性组合都筛掉
    // 2)如果有就跳过
    // 即,在完全背包求方案数的过程中,统计那些初始没有方案数的物品
    
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 110, M = 25010;
    
    int a[N], f[M];
    
    int main()
    {
        int _; cin >> _;
        
        while (_ -- )
        {
            int n;
            cin >> n;
            
            for (int i = 0; i < n; i ++ ) cin >> a[i];
            
            memset(f, 0, sizeof f);
            f[0] = 1;
            
            sort(a, a + n);
            
            //我们只需统计所有物品的体积是否能被其他的线性表出
            //因此背包的体积只需设置为最大的物品体积即可
            //res用来记录最大无关向量组的个数
            
            int m = a[n - 1];
            
            int res = 0;
            for (int i = 0; i < n; i ++ )
            {
                //如果当前物品体积被之前的物品组合线性筛掉了,则它是无效的
                if (f[a[i]]) continue;
                //如果没有被筛掉,则把它加入最大无关向量组
                res ++ ;
                //筛掉当前最大无关向量组能线性表示的体积
                for (int j = a[i]; j <= m; j ++ )
                    f[j] += f[j - a[i]];
            }
            cout << res << endl;
        }
        
        return 0;
    }
    
    

    三、多重背包

    AcWing 6. 多重背包问题 III

    在这里插入图片描述
    当求 j − v j - v jv时其实求的是前面 s s s个长度的窗口中的最大值,“前面 s s s个的最大值“,也就是滑动窗口求极值,再转化为用单调队列求解

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 2e4 + 10;
    
    int f[N], g[N], q[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        
        for (int i = 0; i < n; i ++ )
        {
            int v, w, s;
            cin >> v >> w >> s;
            
            memcpy(g, f, sizeof f);
            
            for (int j = 0; j < v; j ++ )
            {
                int hh = 0, tt = -1;
                for (int k = j; k <= m; k += v)
                {
                    if (hh <= tt && k - q[hh] > s * v) hh ++ ;
                    if (hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
                    while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) /v * w) tt -- ;
                    q[ ++ tt] = k;
                }
            }
        }
        
        cout << f[m] << endl;
    }
    
    

    AcWing 1019. 庆功会

    在这里插入图片描述
    3e7居然过了。

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 6010;
    
    int f[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; i ++ )
        {
            int v, w, s;
            cin >> v >> w >> s;
            for (int j = m; j >= 0; j -- )
                for (int k = 0; k <= s && k * v <= j; k ++ )
                    f[j] = max(f[j], f[j - k * v] + k * w);
        }
        cout << f[m] << endl;
        return 0;
    }
     
    
    

    四、分组背包

    AcWing 1013. 机器分配(打印路径)

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 20;
    
    int f[N][N];
    int w[N][N];
    int way[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                cin >> w[i][j];
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 0; j <= m; j ++ )
            {
                f[i][j] = f[i - 1][j];
                for (int k = 0; k <= m; k ++ )
                    if (j >= k)
                        f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
            }
        
        cout << f[n][m] << endl;
        
        int j = m;
        for (int i = n; i; i -- )
            for (int k = 0; k <= j; k ++ )
                if (f[i][j] == f[i - 1][j - k] + w[i][k])
                {
                    way[i] = k;
                    j -= k;
                    break;
                }
        
        for (int i = 1; i <= n; i ++ ) cout << i << " " << way[i] << endl;
        return 0;
    }
    
    

    五、混合背包

    AcWing 7. 混合背包问题

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <ctime>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define lowbit(x) (x&-x)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    typedef pair<int, int> PII;
    typedef pair<long, long> PLL;
    
    const int N = 1e3 + 10;
    
    int f[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; i ++ )
        {
            int v, w, s;
            cin >> v >> w >> s;
            if (!s)
            {
                for (int j = m; j >= v; j -- )
                    f[j] = max(f[j], f[j - v] + w);
            }
            else
            {
                if (s == -1) s = 1;
                for (int k = 1; k <= s; k *= 2)
                {
                    for (int j = m; j >= k * v; j -- )
                        f[j] = max(f[j], f[j - k * v] + k * w);
                    s -= k;
                }
                if (s > 0)
                    for (int j = m; j >= s * v; j -- )
                        f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
        
        cout << f[m] << endl;
        return 0;
    }
    
    

    六、有依赖的背包问题

    AcWing 10. 有依赖的背包问题

    在这里插入图片描述

    • f [ u ] [ j ] f[u] [j] f[u][j]表示所有从以 u u u为根的子树中选,且总体积不超过 j j j的方案
    • 每棵子树内部以所选体积来划分,也就是说每棵子树内部体积有 m + 1 m+1 m+1种选法,摆脱了 2 k 2^k 2k级别,每一类中取最大即可
    • 在递归考虑每一个节点内部的时候,就转化成了分组背包问题
    • 如何存树 :数组模拟邻接表,且使用单链表;
    • 注意这里根节点不一定是1号点。
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    
    const int N = 110;
    
    int e[N], ne[N], h[N], idx;
    
    int f[N][N];
    int v[N], w[N];
    int n, m;
    
    void add(int a, int b)
    {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }
    
    void dfs(int u)
    {
        for (int i = h[u]; ~i; i = ne[i])       // 循环物品组
        {
            int son = e[i];
            dfs(son);
            
            // 分组背包
            for (int j = m - v[u]; j >= 0; j -- )       // 循环体积
                for (int k = 0; k <= j; k ++ )      // 循环决策
                    f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
        }
        
        // 将物品u加进去
    //    for (int i = v[u]; i <= m; i ++ ) f[u][i] = f[u][i - v[u]] + w[u];
        for (int i = m; i >= v[u]; i -- ) f[u][i] = f[u][i - v[u]] + w[u];
        for (int i = 0; i < v[u]; i ++ ) f[u][i] = 0;
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        
        // 初始化图
        memset(h, -1, sizeof h);
        
        // 找根
        int root;
        
        for (int i = 1; i <= n; i ++ )
        {
            int p;
            scanf("%d%d%d", &v[i], &w[i], &p);
            if (p == -1) root = i;
            else add(p, i);
        }
        
        // 从根开始dfs,而非从1节点开始
        dfs(root);
        
        printf("%d\n", f[root][m]);
        
        return 0;
    }
    
    
    

    AcWing 487. 金明的预算方案

    在这里插入图片描述

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <set>
    #include <map>
    #define endl '\n'
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    using namespace std;
    const double pi = acos(-1);
    typedef long long ll;
    
    typedef pair<int, int> PII;
    
    const int N = 65, M = 32010;
    
    int n, m;
    int f[M];
    PII master[N];
    vector<PII> servant[N];
    
    int main()
    {
        IOS;
        
        cin >> m >> n;
        
        for (int i = 1; i <= n; i ++ )
        {
            int v, p, q;
            cin >> v >> p >> q;
            p *= v;
            if (!q) master[i] = {v, p};
            else servant[q].push_back({v, p});		// servant[q]而非i
        }
        
        for (int i = 1; i <= n; i ++ )
            for (int u = m; u >= 0; u -- )
            {
                for (int j = 0; j < 1 << servant[i].size(); j ++ )
                {
                    int v = master[i].first, w = master[i].second;		// 注意定义的位置不在i层
                    for (int k = 0; k < servant[i].size(); k ++ )
                        if (j >> k & 1)
                        {
                            v += servant[i][k].first;
                            w += servant[i][k].second;
                        }
                    if (u >= v) f[u] = max(f[u], f[u - v] + w);
                }
            }
        
        cout << f[m] << endl;
        
        return 0;
    }
    
    
    
    展开全文
  • 题目:1015. 摘花生 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int ,int >PII; const int N=(1<<11)+10; const int mod=1e9+7;...
  • [AcWing算法提高课]之搜索 双端队列广搜+双向广搜+迭代加深+双向深搜(C++题解)
  • ACWing算法基础

    千次阅读 2021-08-17 10:30:02
    基础算法快速排序 O(nlog⁡n)O(n \log n)O(nlogn)归并排序O(nlog⁡n)O(n\log n)O(nlogn)二分算法O(log⁡n)O(\log n)O(logn)整数二分算法浮点数二分算法高精度 O(n)O(n)O(n)加法减法乘法除法前缀和 O(n)O(n)O(n)初始...
  • 目录位运算64位整数乘法 位运算 64位整数乘法 题意 : 给定a,b(1018)a,b(10^{18})a,b(1018),询问a∗b%pa*b\%pa∗b%p的值 思路 : 我们可以采用类似与快速幂的想法 b=21+22.....+2nb =2^1+2^2.....+2^nb=21+22.....+2n ...
  • AcWing算法基础

    千次阅读 2021-07-10 22:10:08
    目录第一讲 基础算法快速排序AcWing 785. 快速排序AcWing 786. 第k个数归并排序AcWing 787. 归并排序AcWing 788. 逆序对的数量二分AcWing 789. 数的范围AcWing 790. 数的三次方根 第一讲 基础算法 快速排序 AcWing ...
  • AcWing 1049. 大盗阿福 #include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <vector> #include <unordered_map&...
  • 基础的状态压缩点这里 1064. 小国王
  • 培训 在AcWing平台学习算法总结
  • 差分约束知识点讲解例题一:AcWing1169.糖果例题二:AcWing.362 区间例题三:AcWing1170. 排队布局 知识点讲解 差分约束可以求什么: 求不等式组的可行解 如何求最大值或者最小值 Q1:如何求不等式组的可行解 形如:...
  • acwing-提高课

    千次阅读 2021-08-22 17:12:02
    状态机模型) 最小生成树 典型应用: 最小生成树总结 1140 最短网络(python3 prim算法) 1141 局域网(python3 kruskal算法) 1142 繁忙的都市(python3 kruskal算法) 1143 联络员(python3 kruskal算法) 1144 ...
  • [AcWing算法提高课]之 高阶数据结构 并查集(C++题解)
  • } 棋盘覆盖 奇偶格二分图 把所有可以放的格子连一条边,在图中跑匈牙利算法 主要是维护match匹配数组,st标记数组,不太需要真的连边 代码 #include using namespace std; const int N=110; typedef pair,int>pll; ...
  • acwing算法提高课线段树第二部分
  • 本博文主要是记录acwing算法基础第一章基础算法和其模板的相关内容,记录下来供以后复习。
  • acwing算法基础

    千次阅读 2021-10-30 21:06:12
    提高课笔记
  • 算法基础笔记,请支持正版
  • 倍增法 O(mlogn)方法3:Tarjan算法——离线求LCA O(n+m)例题1:AcWing1172.祖孙查询(倍增法)例题2:AcWing1171.距离(Tarjan离线LCA算法) LCA问题 解决方法: 1. 向上标记法 O(n) 从x向上走到根节点, 并标记...
  • 算法提高课。 数字三角形模型 1015摘花生 /*Hello Kitty想摘点花生送给她喜欢的米老鼠。 她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。 地里每个道路的交叉点上都有种着一株...
  • AcWing算法基础 1.1 快速排序 快速排序属于分治算法,快速排序的算法步骤,用分治的思想 确定分界点,数组内任意一个值(这里建议取中点,即(l+r)/2); 调整区间,让x左边的数都小于x,右边的数都大于x; ...
  • Algorithms + Data Structures = Programs.——Niklaus Wirth 本章包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间...AcWing 785. 快速排序 #include<iostream> using nam...
  • 一共三个目录,视频哦有20G+ ,文件中包含下载地址和内容列表。 十大算法 数据结构与算法基础入门 算法导论
  • 1.楼兰图腾 一遍从左边向右边统计,所以当遍历到yi的时候,前面1-i-1个y的高度都已经被加入了树状数组 所以yi左边比它高度低的就是sum(yi-1),左边比它高度高的就是sum(n)-sum(y1) 再一遍从右边向左边统计,所以当...
  • ACWing算法提高课 友好城市 Palmia国有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。 北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。 每对友好城市都向...
  • 组合数学卡特兰数应用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 664
精华内容 265
关键字:

acwing算法提高课