CF DP
detect
·
·
个人记录
CF1271D Portals
法一dp：能到的路径最后选。排序后连接的道路只有O(n)跳，暴力dp均摊后O(n^2)。
法二可回退贪心：每个位置都选，因为每一个城堡都只用一个兵守，如果想反悔了（走不动了）就找到之前最小贡献的位置，撤销这个操作。
CF980D Perfect Groups
每个数把自己的所有平方因子删除，那么剩下的权值必须一样才能分一组。
CF213C Relay Race
### CF930C Teodor is not a liar!
问题等价于问最长的上升下降序列长度，随便数据结构维护max转移即可。
### CF156C Cipher
不变的是字母总和，所以按照长度和字母总和dp。
转移枚举最后一个字母是什么转移即可。
### CF1271E Common Number
把路线画成一棵树，然后把连续的（奇偶两个数合并成一个），树变成了满二叉树（叶子不一定满）。
然后运用二叉树的优秀性质快速统计子树大小即可。
### CF128C Games with Rectangle
长，宽任意选2*k个，每一种选法都对应了恰好一种合法方案，且所有合法方案已定被包块在其内。
### CF1151E Number of Components
在没有环的情况下，联通块数等于点数减去边数。
分开考虑，总点数减去总边数，总边数再转化成一条边被经过多少次，于是可以计算了。
### CF353D Queue
从左至右每一个男生记录其最多等待时间。连续的男生会使等待+1，有女生会使等待-1.
### CF372B Counting Rectangles is Fun
n,m都非常小，询问很大，考虑高位前缀和预处理答案。
处理固定左上，右下以内的所有答案。
然后算左上右下点之间的答案又可以前缀和。
最后$O(1)$输出即可。
### CF771C Bear and Tree Jumps
记录余数，然后换根。
### CF1030E Vasya and Good Sequences
好序列要满足的条件：
1. 1的总和是偶数。
2. 最大的1的个数要小于其他个数之和。
因为一个数最多只有64个1，至少是1，所以每个点暴力枚举前64个位置是否合法，然后就只剩第一条限制，随便预处理即可。
### CF734E Anton and Tree
并查集缩点后，对于直径上每一变化最多减少两个异色，所以下限是直径/2，对于其他附在直径上的点因为深度都小于直径，所以一定会在直径处理完之前先被搞成同色。
答案就是直径/2.
### CF796D Police Stations
每个联通块内都必须有至少一个警察局，因为题目告诉我们当前情况是合法的，因为没有环，所以删一条边会增加一个联通块。
那么答案的上界就是k。
现在考虑构造k的情况，因为题目保证现状一定合法，那么只要每个点被分到离它最近的警局里就行，于是把每个警局bfs染色，最后两点异色的话就可以删。
满足了上界，一定是最优解。
### CF14D Two Paths
枚举边，断开后求两边的直径更新答案。
### CF700B Connecting Universities
总长度=$\sum$每条边经过次数
对于一条边，其左右两边的点数a,b肯定可以经过调整使得有$min(a,b)$条路径经过此边。
### CF165E Compatible Numbers
取反后相当于找子集。
dp预处理所有val的子集答案。
### CF710E Generate a String
$f(i)=min(f(i-1)+x,f(i+1)+x,if(i%2==0) f(i/2)+y)
实际上对于i，如果要使用减操作，一定会由一个*2操作然后一直减回去。
于是f(i)=min(f(i-1)+x,f(j)+y+(j*2-i)*x)
拆开括号可以单调队列。
（其实每次减只会减一次，否则在*2之前减会更优）（于是简单递推也可）
CF1294F Three Paths on a Tree
找出直径，计算剩下的最长链加上就是答案。可以用反证法证明一定包含直径两点。
CF510D Fox And Jumping
题意转换：选出价值最小的几样东西似的其属性gcd为1。
我们考虑枚举一个数，然后考虑如何选取其他的数使得gcd为1且权值最小。
因为一个小于1e9的数最多有10个不同的质因数。
所以对剩下的数状压。
复杂度正确。
CF459E Pashmak and Graph
按边权排序，每次新的边放哪里都必定合法，dp即可，
CF527D Clique Problem
把一个数看成[pos-w,pos+w]的一条线段。
然后题意变成了求不相交的最多线段。
按照右端点排序后扫一遍能放就放一定是最优解（一定不劣）。
CF455B A Lot of Games
建出字典树，如果这剩下链，那么根据奇偶性可以确定谁获得胜利，也就可以树形转移了。
CF505C Mr. Kitayuta, the Treasure Hunter
如果暴力设计dp[i][j]表示前i中最后一次跳跃长度为j的最多收获。
时间空间都不行。
因为这个题现在了每相邻两次跳跃距离变化只能相差1.所以从第一次跳跃起，不同的跳跃长度最多只有约\sqrt{30000}。
所以改变dp状态bdp[i][dal]表示前i的区间最后一次跳跃于第一次跳跃相差dal的最优解。
时空复杂度O(n\sqrt n)
CF547B Mike and Feet
反演的考虑一个位置最多能影响到的区间，两次单调栈算出每个位置左右比其大的第一个数，然后这一段区间大小内的长度都可以被其权值更新。
因为长度都是[1,?]，给?位置打上一个权值标记，倒着扫一遍取min就是每个位置的答案了。
CF883I Photo Processing
二分答案后，考虑如何验证。
以pos为终点，最后一段的起点一定在[L,pos-m+1]，L为满足二分答案的最前端点。
递推过程维护一个前缀方便判断一个区间内是否有以其为结尾的合法解，转移即可。
CF296B Yaroslav and Two Strings
容斥，考虑总方案数减去可比的。
CF229D Towers
每个位置为结尾的最优解是最后一段最小的情况。
维护最优解和最后一段的和，f(i,j)以i结尾的最优解，然后枚举可行的端点转移即可。
CF82D Two out of Three
换一种角度看待问题，前3个人除两个造成的局面必定是当前前两个存在，前面最多只会有一个数没选，dp状态设计成dp(i,j)表示前i个数里一直没选的是第j个数的最优解。
每次操作也就三种转移，可以dp了。
CF847E Packmen
二分答案将问题转化为验证是否合法。
一个人的必须清掉其之前的所有没清掉的垃圾，并且尽可能清完后向后多走。
注意有两种方式，先右后左或者先左后右，取min即可。
CF533B Work Group
奇偶限制十分麻烦，所以多开一维0/1表示子树内选的奇偶。
转移的时候枚举子树边的时候就要不断的更新自己的答案。
最后判断自己选不选，这时候根据题目限制转移即可。
（即使dp状态里没有设合法，但是所有的转移都是在合法的情况下转移的，所以结果一定合法）
CF417D Cunning Gena
按照需要机器数排序后状压dp。
CF960F Pathwalks
每个节点保留历史dp值。
每次更改要找合法（权值递增）的最大dp值。
把权值当做下标，就是查最大值。
那么动态开点即可。
CF893E Counting Arrays
不考虑负数。
质因子之间独立。
那么对于一个质因子p^k就相当于把k个相同的球放进m个不同的盒子。
方案数为C_{m+k-1}^{m-1}。
支持负数的话，发现组合数随表求和拿公式一套即可。
CF797E Array Queries
如果k大于\sqrt n那么暴力枚举不会超过\sqrt n次。
否则只有\sqrt n个不同的k，提前预处理即可。
CF730J Bottles
贪心找出瓶子数后，变成背包，最后要求容量大于一值且选的个数等于某值的最大价值。
CF1067A Array Without Local Maximums
题意有权值限制和左右大小限制。
分别开两维[j][0/1]表示最后一位是j且最后一位是否已经合法的方案数。
可以用前缀和优化。
CF1060E Sergey and Subway
考虑每条边被经过都少次。
答案为所有边的贡献之和/2.
？
不对，如果路径长度为奇数，那还要加1。
现在要求路径为奇数的条数，把树按照层数统计，奇数层到偶数层都是奇数。统计后加入答案即可。
CF940E Cashback
先推一些性质。
-
每一段都是c的倍数，因为不是c的倍数可以拆成c的倍数和一些长度为1的小段，且这样不会劣。
-
长度一定是c，把c的倍数拆成全c，答案一样不会更劣。
那么转移就是区间转移，可以单调队列或者st表。
CF985E Pencils and Boxes
排序后变成序列分段问题。
那么转移的话只用查询上一个合法转移区间内是否有作为结尾的合法状态存在即可。
### CF1012C Hills
设计转台：$f(i,j,0/1)$表示前i个数有j个山峰，最后一个钦定为不是/是山峰。
如果是山峰那么肯定不会减它，且能影响到第i位的是i之前第一个能自由选择的位置。
枚举那个位置的最后一位选还是不选即可转移。
### CF1082E Increasing Frequency
把原本就是c的位置标记出来。
设$f(i,j)$表示线段右端点是i且线段内权值是j的数会变成c的最优解。
考虑i到i+1，如果不是j不是$val_{i+1}$那么不会变。
反之如果是$j==val_{i+1}$，那么转移可以由$val_{i+1}$上一次出现的地方转移。
一次只会对一个权值有修改，那么把第一维压掉后，就是单点更新，每次更新$j$即可。