本文主要是介绍（CSP2019准备）DP专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
T1
LOJ 2063. 「HAOI2016」字符合并
题意
有一个长度为 n n n 的 01 01 01 串，你可以每次将相邻的 k k k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k k k 个字符确定。你需要求出你能获得的最大分数。
1 ≤ n ≤ 300 , 0 ≤ c i ≤ 1 , w i ≥ 1 , k ≤ 8 1 \leq n \leq 300, \ 0 \leq c_i \leq 1, \ w_i \geq 1, \ k \leq 8 1≤n≤300, 0≤ci≤1, wi≥1, k≤8
题解
完全不会区间DP啊，想到最后的串小于8位，记 f [ l ] [ r ] [ s ] f[l][r][s] f[l][r][s]为把 [ l , r ] [l,r] [l,r]合并为s的最大分数，考虑过枚举合并的串，但没法转移为子区间，因为还产生新的字符，于是自闭。
所以一定又是有什么性质没想到啦！想象一下合并的过程，将过程倒一下，发现最后的s倒回去过程中，一直将一个字符展开为一个串，所以s中从左到右每个字符恰好依次对应原串中一段段互不相交的区间！于是枚举s的最后一个字符由哪段区间转移过来即可。
T2
LOJ 2078. 「JSOI2016」无界单词
题意
对于一个单词 S S S ，如果存在一个长度 l l l，满足 0 < l < ∣ S ∣ 0\lt l\lt |S| 0<l<∣S∣，并且使得 S S S 长度为 l l l 的前缀与 S S S 长度为 l l l 的后缀相同，JYY 则称 S S S 是有界的。比如 aabaa 和 ababab 就都是有界的字符串。如果一个单词不存在这样的 l l l ，则 JYY 称之为无界单词。
现在考虑所有仅由字母 a 和 b 组成的长度为 N N N 的字符串，JYY想知道：
- 一共有多少个无界单词？
- 这些无界单词中，按字典序排列第 K K K 小的单词是哪一个？
对于 20 % 20\% 20% 的数据，满足 N ≤ 20 N\le 20 N≤20；
对于全部数据，满足 1 ≤ T ≤ 5 , 1 ≤ N ≤ 64 1\le T\le 5,1\le N\le 64 1≤T≤5,1≤N≤64，并且保证对于任意测试数据，总存在第 K K K 小的无界单词。
题解
为什么每次涉及字符串的题都要乱想半天啊，对字符串一点感觉都没有。。。
对于第一问，考虑用总的减去有界的，记 f [ i ] f[i] f[i]为长度为i的无界单词数量，枚举最短的 l l l，对于 l ≤ n / 2 l\le n/2 l≤n/2显然有 f [ l ] × 2 n − 2 l f[l]\times 2^{n-2l} f[l]×2n−2l种，对于 n / 2 < l n/2<l n/2<l的，想了半天最后发现显然这种情况下还会有更小的 l l l!
对于第二问，容易想到按位算，于是只需考虑在前i位确定的情况下的无界单词数量，依然枚举最小的 l l l，上界仍是 n / 2 n/2 n/2，判断一下已知的部分是否是无界的，以及在已知部分与长度为l的后缀重叠时，重叠部分必须要是已知部分的 n x nx nx指针能跳到的位置。
T3
LOJ 2093. 「ZJOI2016」线段树
题意
小 Yuuka 遇到了一个题目：有一个序列 a 1 , a 2 , … , a n a_1, a_2, \ldots , a_n a1,a2,…,an，对其进行 q q q次操作，每次把一个区间内的数改成区间内的最大值，问最后每个数是多少。
小 Yuuka 很快地就使用了线段树解决了这个问题。于是充满智慧的小 Yuuka 想，如果操作是随机的，即在这 q q q 次操作中每次等概率随机地选择一个区间 [ l , r ] [l,r] [l,r] ( 1 ≤ l ≤ r ≤ n ) (1 \leq l \leq r \leq n) (1≤l≤r≤n)，然后将这个区间内的数改成区间内最大值（注意这样的区间共有 n ( n + 1 ) 2 \frac{n(n+1)}{2} 2n(n+1) 个），最后每个数的期望大小是多少呢？小 Yuuka 非常热爱随机，所以她给出的输入序列也是随机的（随机方式见数据规模和约定）。对于每个数，输出它的期望乘 ( n ( n + 1 ) 2 ) q (\frac{n(n+1)}{2})^q (2n(n+1))q 再对 1 0 9 + 7 10^9+7 109+7 取模的值。
对于所有的测试数据，保证序列中数的大小不超过 1 0 9 10^9 109，即 a i ≤ 1 0 9 a_i≤10^9 ai≤109，并且每个数是 0 0 0 到 1 0 9 10^9 109 之间的随机整数。
n ≤ 400 , q ≤ 400 n \leq 400, \ q \leq 400 n≤400, q≤400。
题解
本来有一个比较奇怪的想法：先考虑一个数对其他数的影响，即在它所能影响的区间内（即最大值为它的极大区间），每次去延伸，可记录左右端点为状态用DP计数。而题目要求的是每个数最后的期望，于是考虑一个数所受到的影响，即将该过程逆过来看，每次受影响的区间也不断扩散，也可用DP计数，但这样效率是 O ( n 4 ) O(n^{4}) O(n4)的，想了半天的优化自闭了 。（要是只求期望和就好了）
所以考虑每个数的期望，效率是有局限的，仍然考虑每个数对其它数的影响。若考虑哪些位置最后刚好变成了这个数，显然不好算。于是考虑容斥，如果考虑变成不小于这个数的话，也难以用差分计算这个数的贡献（不知道次小的是哪个）；而如果是变成不大于这个数，则它的贡献是它与所能影响到的区间的两端最小值的差分，这样对于一个数，若最终变成x，则所有影响范围包含x的数都对它有影响，把最大值的贡献记为它本身，这样的贡献总和就为x，于是就可把每个数的贡献一起用一个区间DP计算了。
T4
LOJ 2136. 「ZJOI2015」地震后的幻想乡
题意
傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。
这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有 n n n 个地方，那么最快的方法当然是修复 n − 1 n-1 n−1 条道路将这 n n n 个地方都连接起来。 幻想乡这 n n n 个地方本来是连通的，一共有 m m m 条边。现在这 m m m 条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第 i i i 条边所需要的时间为 e i e_i ei。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个 e i e_i ei 会是一个 0 0 0 到 1 1 1 之间均匀分布的随机实数。并且所有 e i e_i ei 都是完全独立的。
现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那 n − 1 n-1 n−1 条边，同时开始修复，那么修复完成的时间就是这 n − 1 n-1 n−1 条边的 e i e_i ei 的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边 e i e_i ei 的值，然后再选择完成时间最小的方案。 幽香在走之前，她想知道修复完成的时间的期望是多少呢？
提示：
（以下内容与题意无关，对于解题也不是必要的。）
对于 n n n 个 [ 0 , 1 ] [0,1] [0,1] 之间的随机变量 x 1 , x 2 , . . . , x n x_1,x_2,...,x_n x1,x2,...,xn，第 k k k 小的那个的期望值是 k / ( n + 1 ) k/(n+1) k/(n+1)。
数据范围：
对于所有数据： n ≤ 10 , m ≤ n ( n − 1 ) / 2 , n , m ≥ 1 n \leq 10, \ m \leq n(n-1)/2, \ n,m \geq 1 n≤10, m≤n(n−1)/2, n,m≥1。
对于 15 % 15 \% 15% 的数据： n ≤ 3 n \leq 3 n≤3。
另有 15 % 15 \% 15% 的数据： n ≤ 10 , m = n n \leq 10, m=n n≤10,m=n。
另有 10 % 10 \% 10% 的数据： n ≤ 10 , m = n ( n − 1 ) / 2 n \leq 10, m=n(n-1)/2 n≤10,m=n(n−1)/2。
另有 20 % 20 \% 20% 的数据： n ≤ 5 n \leq 5 n≤5。
另有 20 % 20 \% 20% 的数据： n ≤ 8 n \leq 8 n≤8。
题解
借助提示，题目可转化为一张图最小生成树最大边排名的期望。
形式化一下，设最小生成树最大边排名为 x x x，则前 x − 1 x-1 x−1条边无法使该图联通，而前 x x x条边可以，由此想到容斥，用 x − 1 x-1 x−1条边不行的概率减掉 x x x条边不行的概率即为 x x x条边恰好可以的概率，即只需计算 x x x条边无法使图连通的概率。
又注意到每条边是等价的，于是转化为 x x x条边无法使图连通的方案数，这个又是个经典的套路：连通+不连通=总（易求），而 n n n很小，可以状压： f [ i ] [ s ] f[i][s] f[i][s]为 i i i条边使 s s s不连通的方案数，其中 s s s一定包含1，枚举1所在的连通块，强制其与剩下的点之间没有连边且 s s s联通即可，于是转移到 g [ j ] [ t ] g[j][t] g[j][t]（ j j j条边使 t t t连通）， g g g的转移用总的减去 f f f即可。
T5
LOJ 2139. 「ZJOI2015」幻想乡 Wi-Fi 搭建计划
题意
傲娇少女幽香是一个很萌很萌的妹子。随着科技的进步，幻想乡的大家也开始使用手机了。这时幽香发现没人来她的太阳花田玩了，她感到很伤心，于是向别人打听了一下，才知道原来大家都嫌弃这里没有 Wi-Fi，手机上网还需要流量。
怎么办呢？幽香决定赶快搭建几个 Wi-Fi 点，让所有人都能在太阳花田里畅快地上网。
我们可以近似地把太阳花田看成一个 y y y 轴在 [ 0 , R ] [0,R] [0,R] 之间， x x x 坐标在 ( − ∞ , + ∞ ) (-\infty,+\infty) (−∞,+∞)（也就是在 x x x 轴上无限延伸）的无限长方形。
太阳花田里面有 n n n 个景点，是游客们经常光顾的，幽香认为只要让这些景点尽量被 Wi-Fi 覆盖，那么游客们就肯定心满意足了。
八云紫表示她可以帮幽香架设 Wi-Fi 路由器。现在通用的路由器，每个的覆盖半径正好也是 R R R。八云紫扫视了一遍地图，发现在太阳花田外面，只有 m m m 个有网络的地点，她只可以在那里架设路由器。如果你在点 p p p 搭建了路由器，那么位于 q q q 的地点，只要 p p p 和 q q q 的欧几里得距离小于等于 R R R， q q q 点就会被 Wi-Fi 覆盖。
同时八云紫表示，架设难度随着地点的不同而不同，所以收费也不一样，在第 i i i 个位置架设需要 c i c_i ci 的钱。
现在幽香想要覆盖尽量多的景点，在这个前提下，幽香也想要尽量节省钱。你能帮助她吗？
对于 10 % 10\% 10% 的数据， n , m ≤ 20 n,m\le 20 n,m≤20；
对于另 30 % 30\% 30% 的数据， n , m ≤ 100 n,m\le 100 n,m≤100，所有网络架设点的 y y y 坐标都大于 R R R；
对于另 60 % 60\% 60% 的数据， n , m ≤ 100 n,m\le 100 n,m≤100。
对于全部数据， 1 ≤ R ≤ 1 0 8 , 0 ≤ c ≤ 1 0 4 1\le R\le 10^8,0\le c\le 10^4 1≤R≤108,0≤c≤104。
题解
直接依题意是用最小的权值覆盖所有点，但这不是个多项式复杂可解问题，故考虑有什么性质。
先考虑Wi-Fi只有一边的情况，通过画图发现按x轴排序后，最优方案下每个选中的Wi-Fi覆盖到的是一段连续区间，因为r是相同的，一个Wi-Fi覆盖到的一定是x坐标越靠近越有优势，故不会存在两个点被一个Wi-Fi覆盖时，它们中间的点只能被另一个Wi-Fi覆盖，于是转化为一个经典的DP问题。
这篇关于（CSP2019准备）DP专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
