动态规划课件-mhy12345.PDF

动态规划 mhy12345 动态规划 u 把多阶段过程转化为一系列单阶段问题，利用各阶段之间的 关系，逐个求解. u 解决重复子问题 by mhy12345 分类 u 转移运算 u 状态 u min/max u 线性 u sum u 树形 u Nim 博弈 u 图形 u 概率期望 u 区间 u 状压 u 技巧 u 数位 u 矩阵乘法 u AC 自动机及后缀自动机DP u 记忆化 u 插头 u 数据结构维护 u 单调队列优化 u 斜率优化 u 1D1D 优化 u 四边形优化 by mhy12345 那些动态规划的入门题 dp[i] = dp[j] + 1 by mhy12345 Hanno Tower u 3个柱子，N个圆盘从小到大叠放在A柱子上，求一个移动方 案，使得所有盘子移动到C柱子上，过程中大盘子永远在小 盘子下面。 u 你需要： u 求出方案总数 u 输出最优的一组操作 by mhy12345 越狱 u 监狱有连续编号为1~N 的N 个房间，每个房间关押一个犯人， u 有M 种宗教，每个犯人可能信仰其中一种。 u 如果相邻房间的犯人的宗教相同，就可能发生越狱。 u 求有多少种状态可能发生越狱？ by mhy12345 多重背包问题 u 一个背包容量为m, 有n 件物品. 第i 件物品重wi, 价值vi, 最 多可以装ti 件. 求最大价值和. 背包九讲 by mhy12345 路径问题 u 一个N*M 的方格图，点有权值，还有K个障碍点 （不能走）, 求左上角走到右下角的____. u 路径条数(取模） u N, M =1000 u N, M =10^7; K =20 u N, M = 10^9; P = 10^5; K 20 u 最大路径权值和 u 路径权值模P最大值(P=100) by mhy12345 树的直径 u 给你一个树，求最远两点距离？ u 给你一棵树，输出删掉每条边后剩余两颗子树的直径长度？ by mhy12345 炮兵阵地 u 在个N*M的地图上，有山地和平原 u 在平原上放置炮兵，炮兵可以攻击同行/ 同列距离小于等于2 的8个位置 （不受地形影响） u 给定地图，求放置炮兵方案数 u N=100, M=10