《二轮集训课件dp》由会员分享，可在线阅读，更多相关《二轮集训课件dp（18页珍藏版）》请在金锄头文库上搜索。
1、dp 杂讲 . . . . . . . dp 杂讲 ydc July 7, 2015 dp 杂讲 codeforces 23E tree 给你一棵树，你要把他分成若干个联通块，价值是每个联 通块大小的乘积，最大化价值 原题数据范围：n 700 加强一下：n 100000 dp 杂讲 HAOI2015 T1 有一棵点数为 N 的树，树边有边权。给定 k，你要染黑 k 个点。树的价值是黑点两两之间距离和加白点两两之间距离 和，问最大价值 n 1000 dp 杂讲 APIO2014 Beads and wires 题目戳这里，不记得了 dp 杂讲 总结树形 dp 和普通 dp 类似，设子树信息 转移
2、相当于合并两棵子树 暴力枚举当前子树选几个，看起来是 O(n3) 其实是 O(n2) 的 对于无根树，记个 up 记个 down 大概得到以某个点为根 的答案 dp 杂讲 bzoj 1023 仙人掌图 求一个仙人掌的直径 n 50000 dp 杂讲 Goodbye 2013 G New Year Cactus 一个 n 个点的仙人掌，每个点要被 A 选或被 B 选或不 选，要求 A 选的点不能和 B 选的点相邻，设 a 为 A 选了几 个点，对于 a = 1,2, ,n，求 B 最多能选几个点 n 2500 dp 杂讲 bzoj 1040 骑士 求一个环套树的最大独立集 n 100000 dp
3、 杂讲 总结仙人掌 dp 理解了仙人掌里子树的定义后重新审视状态的定义 对于桥边，和树形 dp 一样转移 对于环，你先不转移，等走到了环顶，再拿环上每个点来 转移 树形 dp 那种暴力枚举子树选几个的方法，在仙人掌上也 是奏效的 dp 杂讲 SCOI Blinker 的仰慕者 n 组数据 一个数的编号是各位之积，求编号为 K 的 A,B 间的数 的个数 A,B,K 1018,n 5000 dp 杂讲 SCOI 火柴棍数字 你有一个 n 位数，用火柴棍来表示，你能移动 k 根火柴， 要最大化得到的数字 n 500,k 3500 dp 杂讲 清华集训 fx 对于 n 位十进制数 x = n1 i=
4、0 ai10i，设 f(x) = n1 i=0 ai2i。 给定 A,B，求 0,B 里有几个数 i 满足 f(i) f(A) A,B 的位数不超过 200 dp 杂讲 总结数位 dp 小技巧：计算小于 n 的答案，把答案转换为 f(r + 1) f(l) 状态一般是， （第 i 位，题目要满足的信息，小于 n 还是 等于 n） 用记忆化搜索写往往思路能更加清晰 dp 杂讲 交与并 蛤蛤上次集训考过了不讲了呢 dp 杂讲 NOI 诗人小 G 你要把 n 数分组，最大化（每组的数字和 -L）的 P 次方 的和 n 100000,P 10 dp 杂讲 NOI 购票 一棵有根树，每次能从一个点 i 跳到他的某个祖先，要求 距离 d 不超过 li，代价是 d pi+ qi n 200000 dp 杂讲 number alpq 的 BC 题 让 n 个数依次进出栈，有 m 个限制条件 A,B 表示 A 必 须比 B 早出栈，问方案数 dp 杂讲 总结 dp 优化 dp 优化实在是种类太多了 dp 优化题目往往是把暴力写在纸上，看能不能用数据结 构优化（包括凸包那种情况） ，如果不能，就看看有没有决策 单调性吧 比如这 4 题中，前两题就是决策单调性，后两题则是数据 结构优化暴力（对于国内 oier，应该更喜欢后者，因为关键 难度在于暴力）
