分享｜ACM_tedukuri_05_动态规划

2023.09.16

2023.12.08

发布于未知归属地

动态规划(69)

1. 线性dp：从初态开始，沿着阶段的扩张向某个方案递推，直至算出目标状态 (lis, lcs, triangle) 最长上升子序列；最长公共子序列；三角形矩阵每次向下或向右移动，最大路径和；

# lis, lcs, tringle trace

1. Mr. Young's Picture Permutations(n个学生排k行队，左端对齐，身高从左到右，从上到下递减，共多少种排队方式，数字三角形排列)

2. LCIS: 最长公共上升子序列(求两个数列的最长公共上升子序列)

3. making the grade(给定序列a，构造长度为n的序列b，满足：b非严格单调，可以递增也可以递减，有重复元素；sum(ai-bi)的值最小)；至少需要修改多少个数？

4. mobile service(指派三个员工到三个地方，指派代价矩阵c(p,q),要求同一时刻只能移动一个员工；相同位置不能有两个员工，按顺序依次指派员工，求最小代价)

5. 传纸条(矩阵中移动，每步只能向右或向下，求最大和要求：两条路径，重复的点位只能算一次)

6. I-country：矩阵中最大凸连通块

7. Cookies: m个饼干，n个孩子，gi为孩子的贪婪度，如果有ai个孩子拿到的饼干比第i个孩子多，第i个孩子的怨气为gi*ai，要求每人最少一块饼干，最小怨气的分配方案

2. 背包问题：总体积不超过最大容量时的最大价值

# coins

1. 数字组合(0/1背包，n个物品，体积价值矩阵为[v,w],容器容量m，不超过最大容量的物品的最大价值正整数序列中子序列和为m的子序列数；n个数，子序列和为m的选择方案数)

2. 自然数拆分Lunatic版(完全背包，n种物品，有无数个，求最大价值)(自然数n拆分成若干个正整数相加的形式，参与加法运算的数允许重复，求拆分方案数)

3. Jury Compromise(n个候选人，m个席位，控方分数d，辩方分数p，总分差绝对值最小，方法不唯一时，选择分值和最大的方案)

4. Coins(多重背包，n种物品，每种c个，求最大价值；n种硬币，面值ai，数量ci，选出若干面值和为s，求1~m间能被拼成的面值有多少？)

5. 分组背包(n组物品，每组c个，每个价值矩阵[v,w],求最大价值)

3. 区间dp：以区间长度作为dp的阶段，使用两个坐标描述每个维度，决策就是划分区间的方法，向下划分，再向上递推，类似线段树

# 石子划分

1. 石子合并：n堆石子，每次合并相邻的两堆，体力消耗为合并的石子重量和，将n堆石子合并为1堆的最小体力消耗

2. Polygon(n边形游戏，第一步删除一条边，之后每一步删除一条边形成的新的节点的值为删除边形成的新的节点的值为删除边及两个端点的节点值计算结果，求最后的最大得分)

3. 金字塔：(给定字符串，abababa对应5种金字塔结构，多叉树dfs序对应的树的结构数)

4. 树形dp： n叉树，对每个节点x，递归在每个子节点上进行dp，回溯时，从子节点向节点x进行状态转移

# 树高，树直径

1. 没有上司的舞会(树形职员关系，没有职员与直接上司参加，职员最大快乐值之和hi)

2. 选课(背包类树形dp，选课学分最多，课程直接先修课最多一门，限制：每门课的先修课程只有一门，两门课的先修课称允许相同，课程不存在时间冲突)

3. Accumulation degree(二次扫描与换根，源点和汇点构成n叉树，节点x,y的容量为c(x,y),流量不超过河道容量，哪个点作为源点时整个水系流量最大)

5. 环形与后效性处理

1. naptime(环形结构动态规划)： i个小时睡觉回复ui点体力，每天n个小时，需要休息8个小时，回复最多体力

2. 环路运输：环形公路，n座仓库，仓库存量ai，两座仓库送货成本ai+aj+dist(i,j),求最大送货成本的两座仓库

3. broken robot(有后效性的状态转移方程)：n*m的棋盘，机器人多轮滚动，等概率停留在原地，左右下移动一格，从起点移动到最后一行的任一位置所需行动次数的数学期望值

6. 计数类dp: 计数问题，强调不重，不漏

# 迭代方式枚举， 指数，组合，排列

1. Gerald and Giant Chess (H*W的棋盘，只有N个格子黑色，左上角到右下角每一步只能向右或向下一格，不能移动到黑色格子中，一共有多少种可能的路线)

2. Connected Graph (求N个节点的无向连通图有多少个)

3. How many of them (无向连通图中，若一条边被删除后，图会分成不连通的两部分，称该边为割边，求满足条件的无向连通图数：由n个节点构成；割边不超过m条；没有自环和重边)

4. A Decorative Fence (N块木板组成长度为N的栅栏，构建栅栏的方案按字典序排序，排名为C的栅栏中各木板从左到右的长度)

7. 数位统计dp

# 数位dp

1. 启示录： (求第x小的魔鬼数，数字的十进制表示中有三个连续的6)

2. 月之迷： (求给定区间内的月之数个数，一个十进制数能被它的各位数字之和整除)

8. 状态压缩优化

# 状压dp

1. Mondriaan's Dream：（N* M的棋盘分割成若干个1*2的长方形，有多少种方案）

3. 炮兵阵地：(N*M 矩阵平面，炮兵阵地攻击上下左右两个距离，不误伤的前提下，最多部署多少阵地)

2. 宝藏：（N个宝藏，M条道路，工程代价最小,避免重复，道路构成一颗树，代价为节点间距离*根节点到目标节点间所有节点数）

倍增优化

2. 开车旅行（AB行程总数比值最小；行驶的总路程）

1. count the repetitions：给定两个字符串s1，s2；两个整数n1，n2；求最大整数m，满足(conn(conn(s2,n2),m) 能由conn(s1,n1))生成，s1和s2长度不超过100，n1 n2不大于10^6

9. 数据结构优化

1. cleaning shifts：(线段树维护花费的最小代价) （白色纸带长度为l，n条贴纸，第i条贴纸可以覆盖ai到bi个格子，售价为ci，若干条贴纸覆盖L-R个格子的最少花费）

2. the battle of chibi：(平衡树复杂，树状数组维护前缀和) (长度为N的数列A，有多少个长度为M的严格递增子序列)

单调队列优化：决策取值范围上下界均单调变化每个决策在候选集合中插入或删除最多依次的问题；单调队列优化多重背包

1. cut the sequence: (长度为n的序列A，把序列分成若干段，在满足每段种所有数的和不超过M的前提下，每段中所有数的最大值之和最小，求该最小值)

2. Fence (N块木板从左到右拍成一行，M个工匠依次粉刷，每块木板最多刷一次，第i个工匠要么不刷，要么刷包含木板Si，长度不超过Li的连续的一段木板，每刷一块可以得到Pi的报酬，安排总报酬最多)

斜率优化：多项式val(i,j)中的每一项仅与i和j中的一个有关使用单调队列优化，包含i，j的乘积项时的优化方式

1. Cat Transport (M只猫，P位饲养员，N座山，第i只猫去Hi号山玩到Ti时刻停止等接，猫的等待时间为0或1，规划饲养员出发时间，使每只猫的等待时间最短)

2. 任务安排（N个任务分成若干批依次执行，第i个任务的执行时间Ti,每批任务开始前需要S的启动时间，执行一批任务所需的时间是启动时间S加每个任务所需时间之和

四边形不等式： w(a,d) + w(b,c) >= w(a,c) + w(b,d)

2. 诗人小G （一维dp）（诗句不协调度尽量小，实际长度与行标准长度差值绝对值的P次方，求最小的不协调度）

1. old stone game （二维dp）(区间和，满足四边形不等式，在p[l,r-1] <= k <= p[l+1,r]的范围内对k进行枚举)

10. exp

1. 乌龟棋(一行n个格子的棋盘，每格一个权值，从起点到终点4中走法，求最大分数)：线性dp

2. 花店橱窗(二维矩阵表示：花在特定花瓶中的美观度，求最大的美观度)：线性dp

3. buy low buy lower(一维数组表示股价序列，统计最长递减子串) 线性dp/统计LIS方案数

4. trip (两个字符串，统计最长公共子串) 线性dp/统计LCS方案数

5. substract(数组间元素相减，相减元素坐标由题目给出，求解特定target需要的相减规则) 线性dp

6. 陨石的秘密(陨石的秘密线性dp; l1 l2 l3 分别代表{} [] (), 求解三种操作对数组的运算结果)线性dp

7. 划分大理石(价值分别为1...6的大理石各a[1...6]块，将它们分成两部分，是两部分价值之和相等，是否可以实现？大理石总数不超过20000) 背包/多重背包

8. Folding(给定字符串，将连续字符计数后压缩) 区间dp

9. 能量项链(特定的珠子顺序，使得珠子首尾相连，释放最大能量)：区间dp/环拆链并复制一倍

10. 棋盘分割(分割8*8的棋盘，使得各矩形棋盘总分的均方差最小)：区间dp/二维平面上的区间dp

11. Blocks(四种颜色的金属块排成一列，相同颜色的相邻金属块合并得分为个数的平方，求一列色块的最大得分)：区间dp

12. Strategic game(n叉树中使用最少节点可以与所有节点相连)：树形dp

13. Bribing FIPA(拥有附属关系的国家无需贿赂，求最少的贿赂数量): 树形dp/背包树形dp

14. Computer(求得树中所有节点到其最远节点的距离)：树形dp/二次扫描与换根法

15. xor和路径()：有后效性dp/高斯消元/数学期望

16. Islands and bridges(找出图中包含最多三角形的hamilton路径): 状态压缩dp

17. corn fields(矩形农场种玉米，不能相邻块种植，，可选择的种植方案数)：状态压缩dp/ 填充网格图形

18. bugs integrated inc(裁剪二维矩阵，避开bug区域，使得裁剪面积尽可能大)：状态压缩dp/ 填充网格图形

19. fence obstacle course()：线段树优化dp

20. estimation()：堆优化dp/中位数

21. 干草堆(给定数组表示干草堆宽度，求解层层叠加的最高高度)：单调队列优化dp/ 贪心

22. 股票交易(给定股价序列，带交易冻结期，求最大profits)：单调队列优化dp

23. largest submatrix(相同字符的最大子矩阵数)：单调队列优化dp

24. k-anonymous sequence()：斜率优化

25. 特别行动队(给定数组表示行动队员战斗力，将相邻队员合并组队使得整体战斗力最大)：斜率优化

26. post office(数轴上建office到所有villages的距离之和最小)：四边形不等式

27. 扑克牌(52张扑克牌，相邻牌面值不同的排列方案数)：计数类dp

28. the counting problem(统计区间内各个数字的出现次数)：数位统计dp

29. round numbers(统计区间内round numbers的个数)：数位统计dp

动态规划(69)

1. 线性dp： 从初态开始，沿着阶段的扩张向某个方案递推，直至算出目标状态 (lis, lcs, triangle) 最长上升子序列；最长公共子序列；三角形矩阵每次向下或向右移动，最大路径和；

1. Mr. Young's Picture Permutations(n个学生排k行队，左端对齐，身高从左到右，从上到下递减，共多少种排队方式，数字三角形排列)

2. LCIS: 最长公共上升子序列(求两个数列的最长公共上升子序列)

3. making the grade(给定序列a，构造长度为n的序列b，满足：b非严格单调，可以递增也可以递减，有重复元素；sum(ai-bi)的值最小)；至少需要修改多少个数？

4. mobile service(指派三个员工到三个地方，指派代价矩阵c(p,q),要求同一时刻只能移动一个员工；相同位置不能有两个员工，按顺序依次指派员工，求最小代价)

5. 传纸条(矩阵中移动，每步只能向右或向下，求最大和 要求：两条路径，重复的点位只能算一次)

6. I-country： 矩阵中最大凸连通块

7. Cookies: m个饼干，n个孩子，gi为孩子的贪婪度，如果有ai个孩子拿到的饼干比第i个孩子多，第i个孩子的怨气为gi*ai，要求每人最少一块饼干，最小怨气的分配方案

2. 背包问题： 总体积不超过最大容量时的最大价值

1. 数字组合(0/1背包，n个物品，体积价值矩阵为[v,w],容器容量m，不超过最大容量的物品的最大价值正整数序列中子序列和为m的子序列数；n个数，子序列和为m的选择方案数)

2. 自然数拆分Lunatic版(完全背包，n种物品，有无数个，求最大价值)(自然数n拆分成若干个正整数相加的形式，参与加法运算的数允许重复，求拆分方案数)

3. Jury Compromise(n个候选人，m个席位，控方分数d，辩方分数p，总分差绝对值最小，方法不唯一时，选择分值和最大的方案)

4. Coins(多重背包，n种物品，每种c个，求最大价值；n种硬币，面值ai，数量ci，选出若干面值和为s，求1~m间能被拼成的面值有多少？)

5. 分组背包(n组物品，每组c个，每个价值矩阵[v,w],求最大价值)

3. 区间dp：以区间长度作为dp的阶段，使用两个坐标描述每个维度，决策就是划分区间的方法，向下划分，再向上递推，类似线段树

1. 石子合并：n堆石子，每次合并相邻的两堆，体力消耗为合并的石子重量和，将n堆石子合并为1堆的最小体力消耗

2. Polygon(n边形游戏，第一步删除一条边，之后每一步删除一条边形成的新的节点的值为删除边形成的新的节点的值为删除边及两个端点的节点值计算结果，求最后的最大得分)

3. 金字塔：(给定字符串，abababa对应5种金字塔结构，多叉树dfs序对应的树的结构数)

4. 树形dp： n叉树，对每个节点x，递归在每个子节点上进行dp，回溯时，从子节点向节点x进行状态转移

1. 没有上司的舞会(树形职员关系，没有职员与直接上司参加，职员最大快乐值之和hi)

2. 选课(背包类树形dp， 选课学分最多，课程直接先修课最多一门，限制：每门课的先修课程只有一门，两门课的先修课称允许相同，课程不存在时间冲突)

3. Accumulation degree(二次扫描与换根，源点和汇点构成n叉树，节点x,y的容量为c(x,y),流量不超过河道容量，哪个点作为源点时整个水系流量最大)

5. 环形与后效性处理

1. naptime(环形结构动态规划)： i个小时睡觉回复ui点体力，每天n个小时，需要休息8个小时，回复最多体力

2. 环路运输： 环形公路，n座仓库，仓库存量ai，两座仓库送货成本ai+aj+dist(i,j),求最大送货成本的两座仓库

3. broken robot(有后效性的状态转移方程)：n*m的棋盘，机器人多轮滚动，等概率停留在原地，左右下移动一格，从起点移动到最后一行的任一位置所需行动次数的数学期望值

6. 计数类dp: 计数问题，强调不重，不漏

1. Gerald and Giant Chess (H*W的棋盘，只有N个格子黑色，左上角到右下角每一步只能向右或向下一格，不能移动到黑色格子中，一共有多少种可能的路线)

2. Connected Graph (求N个节点的无向连通图有多少个)

3. How many of them (无向连通图中，若一条边被删除后，图会分成不连通的两部分，称该边为割边，求满足条件的无向连通图数：由n个节点构成；割边不超过m条；没有自环和重边)

4. A Decorative Fence (N块木板组成长度为N的栅栏，构建栅栏的方案按字典序排序，排名为C的栅栏中各木板从左到右的长度)

7. 数位统计dp

1. 启示录： (求第x小的魔鬼数，数字的十进制表示中有三个连续的6)

2. 月之迷： (求给定区间内的月之数个数，一个十进制数能被它的各位数字之和整除)

8. 状态压缩优化

1. Mondriaan's Dream：（N* M的棋盘分割成若干个1*2的长方形，有多少种方案）

3. 炮兵阵地：(N*M 矩阵平面，炮兵阵地攻击上下左右两个距离，不误伤的前提下，最多部署多少阵地)

2. 宝藏：（N个宝藏，M条道路，工程代价最小,避免重复，道路构成一颗树，代价为节点间距离*根节点到目标节点间所有节点数）

倍增优化

2. 开车旅行 （AB行程总数比值最小；行驶的总路程）

1. count the repetitions： 给定两个字符串s1，s2；两个整数n1，n2；求最大整数m，满足(conn(conn(s2,n2),m) 能由conn(s1,n1))生成，s1和s2长度不超过100，n1 n2不大于10^6

9. 数据结构优化

1. cleaning shifts：(线段树维护花费的最小代价) （白色纸带长度为l，n条贴纸，第i条贴纸可以覆盖ai到bi个格子，售价为ci，若干条贴纸覆盖L-R个格子的最少花费）

2. the battle of chibi：(平衡树复杂，树状数组维护前缀和) (长度为N的数列A，有多少个长度为M的严格递增子序列)

单调队列优化： 决策取值范围上下界均单调变化每个决策在候选集合中插入或删除最多依次的问题； 单调队列优化多重背包

1. cut the sequence: (长度为n的序列A，把序列分成若干段，在满足每段种所有数的和不超过M的前提下，每段中所有数的最大值之和最小，求该最小值)

2. Fence (N块木板从左到右拍成一行，M个工匠依次粉刷，每块木板最多刷一次，第i个工匠要么不刷，要么刷包含木板Si，长度不超过Li的连续的一段木板，每刷一块可以得到Pi的报酬，安排总报酬最多)

斜率优化： 多项式val(i,j)中的每一项仅与i和j中的一个有关使用单调队列优化，包含i，j的乘积项时的优化方式

1. Cat Transport (M只猫，P位饲养员，N座山，第i只猫去Hi号山玩到Ti时刻停止等接，猫的等待时间为0或1，规划饲养员出发时间，使每只猫的等待时间最短)

2. 任务安排 （N个任务分成若干批依次执行，第i个任务的执行时间Ti,每批任务开始前需要S的启动时间，执行一批任务所需的时间是启动时间S加每个任务所需时间之和

四边形不等式： w(a,d) + w(b,c) >= w(a,c) + w(b,d)

2. 诗人小G （一维dp） （诗句不协调度尽量小，实际长度与行标准长度差值绝对值的P次方，求最小的不协调度）

1. old stone game （二维dp）(区间和，满足四边形不等式，在p[l,r-1] <= k <= p[l+1,r]的范围内对k进行枚举)

10. exp

1. 乌龟棋(一行n个格子的棋盘，每格一个权值，从起点到终点4中走法，求最大分数)： 线性dp

2. 花店橱窗(二维矩阵表示：花在特定花瓶中的美观度，求最大的美观度)： 线性dp

3. buy low buy lower(一维数组表示股价序列，统计最长递减子串) 线性dp/统计LIS方案数

4. trip (两个字符串，统计最长公共子串) 线性dp/统计LCS方案数

5. substract(数组间元素相减，相减元素坐标由题目给出，求解特定target需要的相减规则) 线性dp

6. 陨石的秘密(陨石的秘密 线性dp; l1 l2 l3 分别代表{} [] (), 求解三种操作对数组的运算结果)线性dp

7. 划分大理石(价值分别为1...6的大理石各a[1...6]块，将它们分成两部分，是两部分价值之和相等，是否可以实现？大理石总数不超过20000) 背包/多重背包

8. Folding(给定字符串，将连续字符计数后压缩) 区间dp

9. 能量项链(特定的珠子顺序，使得珠子首尾相连，释放最大能量)： 区间dp/环拆链并复制一倍

10. 棋盘分割(分割8*8的棋盘，使得各矩形棋盘总分的均方差最小)： 区间dp/二维平面上的区间dp

11. Blocks(四种颜色的金属块排成一列，相同颜色的相邻金属块合并得分为个数的平方，求一列色块的最大得分)： 区间dp

12. Strategic game(n叉树中使用最少节点可以与所有节点相连)： 树形dp

13. Bribing FIPA(拥有附属关系的国家无需贿赂，求最少的贿赂数量): 树形dp/背包树形dp

14. Computer(求得树中所有节点到其最远节点的距离)： 树形dp/二次扫描与换根法

15. xor和路径()： 有后效性dp/高斯消元/数学期望

16. Islands and bridges(找出图中包含最多三角形的hamilton路径): 状态压缩dp

17. corn fields(矩形农场种玉米，不能相邻块种植，，可选择的种植方案数)： 状态压缩dp/ 填充网格图形

18. bugs integrated inc(裁剪二维矩阵，避开bug区域，使得裁剪面积尽可能大)： 状态压缩dp/ 填充网格图形

19. fence obstacle course()： 线段树优化dp

20. estimation()： 堆优化dp/中位数

21. 干草堆(给定数组表示干草堆宽度，求解层层叠加的最高高度)： 单调队列优化dp/ 贪心

22. 股票交易(给定股价序列，带交易冻结期，求最大profits)： 单调队列优化dp

23. largest submatrix(相同字符的最大子矩阵数)： 单调队列优化dp

24. k-anonymous sequence()： 斜率优化

25. 特别行动队(给定数组表示行动队员战斗力，将相邻队员合并组队使得整体战斗力最大)： 斜率优化

1. 线性dp：从初态开始，沿着阶段的扩张向某个方案递推，直至算出目标状态 (lis, lcs, triangle) 最长上升子序列；最长公共子序列；三角形矩阵每次向下或向右移动，最大路径和；

5. 传纸条(矩阵中移动，每步只能向右或向下，求最大和要求：两条路径，重复的点位只能算一次)

6. I-country：矩阵中最大凸连通块

2. 背包问题：总体积不超过最大容量时的最大价值

2. 选课(背包类树形dp，选课学分最多，课程直接先修课最多一门，限制：每门课的先修课程只有一门，两门课的先修课称允许相同，课程不存在时间冲突)

2. 环路运输：环形公路，n座仓库，仓库存量ai，两座仓库送货成本ai+aj+dist(i,j),求最大送货成本的两座仓库

2. 开车旅行（AB行程总数比值最小；行驶的总路程）

1. count the repetitions：给定两个字符串s1，s2；两个整数n1，n2；求最大整数m，满足(conn(conn(s2,n2),m) 能由conn(s1,n1))生成，s1和s2长度不超过100，n1 n2不大于10^6

单调队列优化：决策取值范围上下界均单调变化每个决策在候选集合中插入或删除最多依次的问题；单调队列优化多重背包

斜率优化：多项式val(i,j)中的每一项仅与i和j中的一个有关使用单调队列优化，包含i，j的乘积项时的优化方式

2. 任务安排（N个任务分成若干批依次执行，第i个任务的执行时间Ti,每批任务开始前需要S的启动时间，执行一批任务所需的时间是启动时间S加每个任务所需时间之和

2. 诗人小G （一维dp）（诗句不协调度尽量小，实际长度与行标准长度差值绝对值的P次方，求最小的不协调度）

1. 乌龟棋(一行n个格子的棋盘，每格一个权值，从起点到终点4中走法，求最大分数)：线性dp

2. 花店橱窗(二维矩阵表示：花在特定花瓶中的美观度，求最大的美观度)：线性dp

6. 陨石的秘密(陨石的秘密线性dp; l1 l2 l3 分别代表{} [] (), 求解三种操作对数组的运算结果)线性dp

9. 能量项链(特定的珠子顺序，使得珠子首尾相连，释放最大能量)：区间dp/环拆链并复制一倍

10. 棋盘分割(分割8*8的棋盘，使得各矩形棋盘总分的均方差最小)：区间dp/二维平面上的区间dp

11. Blocks(四种颜色的金属块排成一列，相同颜色的相邻金属块合并得分为个数的平方，求一列色块的最大得分)：区间dp

12. Strategic game(n叉树中使用最少节点可以与所有节点相连)：树形dp

14. Computer(求得树中所有节点到其最远节点的距离)：树形dp/二次扫描与换根法

15. xor和路径()：有后效性dp/高斯消元/数学期望

17. corn fields(矩形农场种玉米，不能相邻块种植，，可选择的种植方案数)：状态压缩dp/ 填充网格图形

18. bugs integrated inc(裁剪二维矩阵，避开bug区域，使得裁剪面积尽可能大)：状态压缩dp/ 填充网格图形

19. fence obstacle course()：线段树优化dp

20. estimation()：堆优化dp/中位数

21. 干草堆(给定数组表示干草堆宽度，求解层层叠加的最高高度)：单调队列优化dp/ 贪心

22. 股票交易(给定股价序列，带交易冻结期，求最大profits)：单调队列优化dp

23. largest submatrix(相同字符的最大子矩阵数)：单调队列优化dp

24. k-anonymous sequence()：斜率优化

25. 特别行动队(给定数组表示行动队员战斗力，将相邻队员合并组队使得整体战斗力最大)：斜率优化

26. post office(数轴上建office到所有villages的距离之和最小)：四边形不等式

27. 扑克牌(52张扑克牌，相邻牌面值不同的排列方案数)：计数类dp

28. the counting problem(统计区间内各个数字的出现次数)：数位统计dp

29. round numbers(统计区间内round numbers的个数)：数位统计dp