$2019$ 暑期刷题记录1:(算法竞赛DP练习)

$ 2019 $ 暑期刷题记录:

$ POJ~1952~~BUY~LOW, BUY~LOWER: $ （复杂度优化）

题目大意：统计可重序列中最长上升子序列的方案数。

题目很直接的说明了所求为 $ LIS $ 的方案数
但是题目给出的元素是会重复的，结果需要去重
用 $ n^2 $ 的动态规划再另建数组记录方案可以秒杀
如果要优化复杂度就必须用求 $ LIS $ 的 $ nlogn $ 算法，其中树状数组符合要求

$ POJ~1934~~Trip: $ （方案输出）

题目大意：输出两个序列中最长公共子序列的所有方案。

可重序列的最长公共子序列目前最低复杂度也是 $ n^2 $
但是 $ n^2 $ 求最长公共子序列用的是DP，会产生覆盖，难以不重不漏的得到所有合法方案
但是这道题是一道字符串，元素只有26种，我们可以从这里下手
于是我们从最长公共子序列的本质出发，预处理出从某一字母到其他字母的最近位置
然后向前匹配，只要跳转时对应的 $ F[i][j] $ 为当前最优值-1即为合法方案。
为了方便，我们可以递归搜寻

$ POJ~1722~~SUBTRACT: $ （题目特性，结论）

题目大意：有一个数列，每次可以将其中相邻的两个以取差的方式合并，直到只剩一个数。现给出初始数列，和最终结果，求任意一种可行方案。 $ nleq100~,~a_ileq100~,~Tin[-10000,+10000] $

当时看这题第一眼就猜了个结论：每一个数都可以通过操作随意加减，直接背包。
但是后来仔细一看，第一个数就不可以。于是将自己否定了。
但是没有这个结论线性DP寸步难行，所以这题一定有玄机
仔细分析可以发现其实就第一个数必须为负，其他数便可以在它的基础上达到可加可减的效果（所以结论是对的）
因为只牵扯到能和不能，所以我们用 $ bitset $ （二进制优化）来01背包，一下就能跑到最优解。

$ POJ~1187~ imes ~ $ 陨石的秘密：（找基准点）（记忆化化索）

题目大意：对于一个由大中小括号组成的字符串，它所含的大括号不能被中小括号括起来，中括号不能被小括号括起来。这个字符串的深度即为括号层数。现在给出大中小括号的数目及深度，求有多少中合法字符串。

这道题首先我们可以将括号字符串用树的形式表示出来（其中子树要按顺序排列）
结合这个思想我们发现要保证字符串之间补充不漏，就要找一个基准点
于是我们将所求字符串分为两部分，第一部分一定被一个括号括起来，第二个部分只要合法即可
于是我们只要枚举确定第一部分，就能补充不漏的计算所有的情况
然后我们发现第一部分除去最外层括号就成了一个子问题，而第二个部分本身就是一个子问题
于是我们想到递归（即记忆化搜索），将第一部分和第二部分化为两个子问题向下递归，只是第一部分的最外层括号需要讨论一下（因为它可以填大中小三种，不过必须先符合要求）

$ CH5E07: $ 划分大理石（多重背包的优化）

题目大意：有价值分别为1..6的大理石各a[1..6]块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。大理石的总数不超过20000。

已经不要太明显了，这是一道完全背包。
我们求出左右这些大理石能表示出的价值，如果存在两个价值是1:2就说明可以分成两部分
就是数据范围有点大，于是我们考虑多重背包的优化（二进制拆分）（单调队列）
然后。。。。。连码代码博主都不想了

$ POJ~2176~~Folding: $ （预处理）

题目大意：给你一个由大写字母组成的字符串，其中连续重复的一段可以进行折叠（详细见题面），现在要你求折叠之后长度最小的方案。

这道题首先可以猜想是不是线性DP，然后发现数据范围比较友好，可以 $ n^2 $
于是这几乎变成了一道傻逼题：设 $ f[i] $ 表示前i个字符的最短表达方案， $ g[i][j] $ 表示 $ i $ 到 $ j $ 的最短表达式
$ f[i]=sum_{k=0}^{k<i}f[k]+g[k+1][i] $ 这个里面的 $ g[k+1][i] $ 暴力求即可。

$ POJ~1191~~ $ 棋盘分割：（化简所求式）（二维区间DP）

题目大意：有一个 $ 8 imes8 $ 的棋盘，每一个格子都有一个权值，你有 $ n-1 $ 次操作，每一次操作可以讲一个独立矩阵切成两个独立矩阵（只能横竖切）。你需要求出最后 $ n $ 个矩阵的可能的最小方差。（每一个矩阵的权值为它包含的所有格子的权值和）

这道题当时想的是01分数规划，或者二分答案。
但是这道题所求的式子比较复杂，难以判断，不好优化。
所以我门只能化简这个式子（或者从棋盘本身的性质下手）
而化简完这个式子后我门发现只要所有独立矩阵的权值平方和最小即可
于是这就变成了一道经典的二维区间DP，数据范围很小，连优化都不需要

$ POJ~1390~~Blocks: $ （很难想的区间DP）

题目大意： 有一个数列，你可以选择其中连续的一段相同数字将它们消掉，得分为相同数字个数的平方。现在给出初始序列，求最高得分。

$ POJ~1463~~Strategic~game: $ （树形DP）

题目大意：有一颗树，你可以在某些节点上放一个守卫，他可以保护所有与这个节点直接连接的节点。现在给出这可树，让你求出最少放多少守卫使每一个节点都被守护。

这道题比较简单。
可以直接按照拓扑排序的思想从叶子节点出发，在叶子节点的上一个节点放守卫，这样一定最优
当然我们也可以树形DP，设状态：每一个节点放或不放守卫时，其对应子树的最小守卫数。

$ POJ~3345~~Bribing~FIPA: $ （背包类树形DP）

题目大意：有 $ n $ 个国家，它们附庸关系构成一棵树，每个国家有一个贿赂值，如果你贿赂了其中某一个国家，就等于贿赂了所有附庸于它的国家（就是这一整颗子树）。现在要求你贿赂 $ m $ 个国家，求最小花费。

首先建立一个虚根，将所有树连在一起
然后就是很明显的树形DP了，但是它的转移类似于分组背包
每一个节点的信息需要各个子节点以分组背包的形式得出：
设 $ f[i][j] $ 表示第 $ i $ 个节点的子树里贿赂 $ j $ 个节点的最小花费，转移就是分组背包

$ HDOJ~2196~~Computer: $ （二次扫描与换根法）

题目大意： 给你一颗树，每一条边都有权值，现在你需要求出每一个节点到与它距离最远的节点的距离。

这道题还是比较简单的，至少比书上例题还要明显
我们可以先树形DP（默认一个点为根），求出每一个节点到它作为根的子树里最远的节点
然后直接暴力换根就可以了

$ BZOJ~2337~~ $ XOR和路径：（方案输出）

题目大意： 有一个无相连通图，边权为非负整数，现在从一号节点出发，等概率走向与它相连的节点，求从 $ 1 $ 号节点到 $ n $ 的路径上每个边权的异或和的期望。 $ nleq100 $

比书上例题简单多了！
我们对于在每一个节点的下一步路径，列一个当前节点到 $ n $ 的期望方程
发现 $ n $ 个节点就构成了一个高斯消元方程组，数据范围小，直接高斯消元即可。

$ POJ~3254~~Corn~Fields: $ （状态压缩）

题目大意： 有一个 $ n imes m $ 的方田，其中有一些格子土地贫瘠无法种植，现在需要在方田里种玉米，要求所有玉米不相邻，求有多少种种植方案。 $ 1leq n,m leq12 $

炮兵阵地的弱化版，一个套路
先预处理出一行的所有种植方案（玉米不能相邻）
然后用一个二进制表示能不能种（土地本身贫瘠）（上一个格子种了玉米）
然后直接从第一行开始状压DP即可，用种植方案和能不能种两个二进制或运算，还有1，就代表有冲突。

$ POJ~1038~~ imes Bugs~Integrated~Inc: $ （复杂的状压DP）

很有意思的一道题目，比较有代表性，就单独列一篇题解了，这是传送门。

$ POJ~2374~~Fence Obstacle Course: $ （类扫描线）（线段树建图）（线段树优化DP转移）

题目大意： 从一个二维平面的顶端竖直向下坠落，每一行都有一个水平挡板，只有左右移动到挡板两端才能继续下落，终点在最下端中心，求最少的向左向右移的步数。整个二维平面长宽为 $ 1 imes 10^5 $ 级别。

这道题如果是 $ n^2 $ 就很好做。
设 $ f[i][j] $ 表示在水平位置 $ i $ 行第 $ j $ 列时最少左右移的步数。
然后直接按照挡板位置，暴力转移：挡板上的 $ f[i][j] $ 都要转移到挡板两端。
这道题当时自己想到了线段树，但却是用来区间求最小值优化转移的，可行是可行，但比网上大佬弱多了
这道的优化集中在挡板的一个性质：一个挡板的端点状态一定只会转移到唯一一个它下面的挡板上
根据这个一一对应的原则，然后挡板的端点只有 $ 2n $ 个，所以转移应该也只有 $ 2n $ 次
我们可以用扫描线的思想，用线段树来记录挡板的端点信息，然后找到挡板间的精确转移顺序
然后我们就可以用它来跑图论最短路，或者做到DP的快速转移，（也可以更改权值）

$ HDOJ~4261~~Estimation: $ （优先队列求中位数）

题目大意： 给定一个长度为N的整数数组 $ A $ ，你需要创建另一个长度为 $ N $ 的整数数组 $ B $ ，数组 $ B $ 被分为 $ K $ 个连续的部分，并且如果i和j在同一个部分，则 $ B[i]=B[j] $ 。现要求数组 $ B $ 能够满足 $ Σ|A[i]-B[i]| $ 最小，请你输出这个最小值。 $ 1≤N≤2000~,~1≤K≤25~,~K≤N $

这道题我们可以很明显的发现一个结论： $ B $ 数组的元素一定在 $ A $ 数组中出现过
然后我们就设 $ f[i][j] $ 表示前 $ i $ 个数分为 $ j $ 段的最小值。
$ f[i][j]=f[k][j-1]+s[k+1][j] $
其中 $ s[k+1][j] $ 表示区间 $ [k+1,j] $ 选最佳数字，所产生的“费用”
这个 $ s $ 数组显然可以预处理：我们将一段区间所有元素换成 $ A $ 中元素后的大小排序，这段区间和在这个排序中最接近的值即可。(虽然网上大多都用优先队列求中位数的方案来预处理，但这样似乎更方便)
居然自己想出来了，好开心！

$ BZOJ~1855~~ $ 股票交易：（较复杂的单调队列）

$ HDOJ~2870~~Largest~Submatrix: $ （悬线法）

题目大意： 给定一个由字母 $ ’a’ $ ， $ ’b’ $ ， $ ’c’ $ ， $ ’w’ $ ， $ ’x’ $ ， $ ’y’ $ ， $ ’z’ $ 构成的矩阵，你可以将 $ ’w’ $ 改为 $ ’a’ $ 或 $ ’b’ $ ，将 $ ’x’ $ 更改为 $ ’b’ $ 或 $ ’c’ $ ，将 $ ’y’ $ 更改为 $ ’a’ $ 或 $ ’c’ $ ，将 $ ’z’ $ 更改为 $ ’a’ $ ， $ ’b’ $ 或 $ ’c’ $ 。请你求出通过更改矩阵，可以得到的由相同字母构成的最大子矩阵。 $ 1≤m,n≤1000 $

很明显的一道题目。
最大的子矩阵只能全是 $ a,b,c $ 中的一种
于是我们分三种情况讨论，每一次将所有能转换的字母都转换成同一种字母
然后直接悬线法扫一遍，复杂度 $ 3 imes n^2 $

$ POJ~3709~~K-Anonymous~Sequence: $ （斜率优化）

题目大意： 给出一个长度为n的非严格递增整数序列，每次操作可以将其中的一个数减少一，问最少多少次操作后能够使得序列中的任何一个数在序列中都至少有k-1个数与之相同。

很明显的一道题，表示在 $ cut~the~sequence $ 面前，这道题就是个小弟
设 $ F[i] $ 表示前 $ i-1 $ （减个一方便）个数分组后的最小操作次数：
$ F[i]=min{F[k]+(S[i-1]-S[k])-A[k] imes (i-k) } $
$ F[i]=F[k]-S[k]+A[k] imes k+S[i-1]-A[k] imes i $
$ F[k]-S[k]+A[k] imes k=-A[k] imes i+F[i]+S[i-1] $
然后直接斜率优化一下就好

$ BZOJ~1911~ imes ~ $ 特别行动队：（斜率优化）

很有意思的一道题目，比较有代表性，就单独列一篇题解了，这是传送门。

$ POJ~1160~~Post~Office: $ （四边形不等式）

题目大意： 一条笔直的高速公路上有N个村庄，每个村庄都有一个整数位置坐标，不同村庄的坐标不同，现在要在高速公路上建立P个邮局。请问如何安排邮局的位置可以使得每个村庄到其最近邮局的距离和最小，输出这个最小值。

这简直和之前那道 $ HDOJ~4261~~Estimation: $ （优先队列求中位数）一模一样
这道题还简单些，数据范围太小了，直接暴力都没问题
但是如果要让复杂度进一部优化，就需要四边形不等式了！

$ CH~5E26~ imes ~ $ 扑克牌：（计数类DP）

很有意思的一道题目，比较有代表性，就单独列一篇题解了，这是传送门。

$ POJ~2282~~The Counting Problem: $ （数位DP）

题目大意： 给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0~9的出现次数。

因为逼近的惯用套路，我们选择数位长度做第一维
然后第二维就可以是长度为 $ i $ 的数里有包含多少个数字 $ j $
转移的时候需要注意当前最前面的数字为多少，要特判+1
求答案时可以求 $ [0,a] $ 和 $ [0,b] $ 取差得出答案，方便快捷。

$ POJ~3252~~Round~Numbers: $ （数位DP）

题目大意： 把一个十进制数转换为一个无符号二进制数，若该二进制数中0的个数大于或等于1的个数，则它就是一个圆形数字。现在给定两个正整数a和b，请问在区间[a,b]内有多少个圆形数字。

这个其实就是二进制下的数位DP
老惯例，设位二进制长度为DP第一层循环
其次我们肯定要记录1的个数与0的个数的差值
这个可以用两个数组搞（一个1多，一个0多），然后递推时根据当前位是1或0,来分开转移
然后逼近的时候，可以将问题转换一下，可以求 $ [0,a] $ 和 $ [0,b] $ 内的答案再取差得出最终答案
然后就是前缀和要处理好，当前 $ i $ 位为1时，所有长度小于 $ i $ 的有效数都是有贡献的！