自己想的时候一直在纠结的问题是怎么保存(第k个之前的是不是0/1)的问题，纠结了很久没有get到正点上，因为单单这样的话似乎会导致状态信息不足。。会漏掉一些情况。看了绿书题解，一看到状压顿时明白了。。。k最大只有10，这样的话只要把构造串的最后k位01情况压缩起来就可以了。另外一个问题就是这样的话会不会导致有中间产生长度超过k的回文串，答案是否定的，因为回文串本身其实有着子结构的性质，如果以某个节点为最后一位的长度k的回文串没有被构造出来，那么一定不会有更长的回文串包含这个点的。
[CF][DP][递推关系] codeforces 1068D Array Without Local Maximums
嗯。。。。果然还是那句话，直接上组合数学搞不定的组合数学，要么打表要么dp递推。
设dp[i][j][flag]表示前i数字，令最后一个数字为j时的方法数，其中flag==0表示第i-1个比第i个小，flag==1表示第i-1大于等于第i个，然后根据题目要求就是不能出现局部极大值，所以可以写出来递推式：① dp[i][j][0]=Σ(dp[i-1][k][0]+dp[i-1][k][1]) ,1<=k<j ② dp[i][j][1]=dp[i-1][j][0]+Σdp[i-1][k][1],j<=k<=200 边界条件的话是单独考虑i==1的时候，特判算一下就可以了。这个方法是n*200个状态，每次转移再*200就是40000*n，太慢，观察到是求前缀/后缀和的形式，可以每一轮算完i之后维护一个presum[j][flag]，保存这一轮的前缀和，这样的话可以O(1)转移，复杂度就变成了n*200 。
主要的思考的点就在于在满足题目条件的约束下递推，加了一维状态表示之后问题就变得很简单了，所以推不出来的时候可以考虑加维（增加dp的信息量）
由于偷懒到处取模所以代码很慢吧。。。不过dp重要的是思想hhh
继续阅读“[CF][DP][递推关系] codeforces 1068D Array Without Local Maximums”
[treeDp][状态分析][dfs] UVa12093 Protecting Zonk
这个题确实是，自己想没有整出来。由于多考虑了一层，状态变得复杂了。
首先还是转化为有根树去做，然后考虑下自底向上的推法。因为这里多考虑一层，所以还需要考虑子节点的放置情况，也就是除了考虑i节点放A/放B/不放，还需要考虑i的子节点，有没有放B/放A/不放，这样的话可以发现所有的情况到最后可以归类为4类，1）i处放B 2）i处放A且子节点放A/放B/没但是其字节点全放A/B，或者i处不放，其字节点至少有一个放B 3）i处不放，但是子节点全为2状态 4）能保证父节点放一个B就能覆盖到往下所有未覆盖路径的任意状态。然后就可以把状态转移方程搞出来，记忆化搜索即可。
自己思考存在的问题：脱离了无后效性这个基本点在想。如果按照一遍dfs来dp的思路，应该是保证了子树推出来之后才能推更高的祖先。
wa的话，因为用了一个cur的变量，之后再用却没有正确赋值。。。
[数位+状压][DP] codeforces 1073E Segment Sum
这场前四个的难度跟后面的完全不是一个div的。。。abcd都很容易出的那种。。
然后今天这个E，怎么说，思路很容易想到，一看就是数位dp，然后也比较容易发现需要保存已经用过的数字集合，所以一个下标是状压的二进制。
然后我以为就这么开心的做了，但是操蛋的是，这个需要考虑很多前导0的情况。。然后我就写炸了。。。调了巨久。。。基本上后来就是各种特殊情况往上加，呵呵，虽然最后1y但是对我来说感觉做出来跟没做出来已经没什么区别了，浪费了n个小时（本来该看射频的啊啊啊啊啊啊啊啊凉凉
丑陋的各种特判代码先放这儿，等我去扒一扒前排大佬代码（其实cf那场也就不到100人A了这个题 继续阅读“[数位+状压][DP] codeforces 1073E Segment Sum”
[比赛][TreeDP][树的性质][换轴][统计技巧] codeforces 1060E Sergey and Subway
自己思路的问题：每次用一个中转节点多连一条线就是等于跳过了一个节点，想到了偶数就是/2，奇数是+1/2，但是没有想到怎么去统计实现。
这个问题最后的答案可以表示为（S+O)/2，其中S是所有点对之间的路径长度之和，O是路径长度为奇数的路径的数量。然后就是如何计算这两个数字的问题。
我以前的理解是求S得用两遍dfs的treeDP，然而这次学到了新操作就是可以分别考察每一条边他被多少对点之间的路径包含了，只需要求出有根树每个点对应的子树中的节点个数即可，S+=(n-subts[x])*subs[x]。
求O的方法就更妙了，画出来一颗有根树就可以发现，两个节点之间的距离奇偶性可以用他们到根节点的奇偶性来表示！（因为树形结构本身对于根节点来说有某种意义上的差分性质emmm），假如两个点到root的路径长度（也就是depth）奇偶性相同，那么他们之间的路径就是偶数的否则是奇的。所以只需要求出来所有的奇数层的节点个数乘以所有的偶数层的节点个数就可以得到O了。
继续阅读“[比赛][TreeDP][树的性质][换轴][统计技巧] codeforces 1060E Sergey and Subway”
[二维平面离散点的DP][离散化] 2018camp day1 Growth
http://newoj.acmclub.cn/problems/2057
看的时候没有什么思路，想过dp但是感觉数据量不可行，看了题解才意识到离散化即可O(n^2)，暴力刷表推出来每个点的最优值即可。
此外，还学习到了v[i][j]=v[i][j-1]+v[i-1][j]-v[i-1][j-1]+mp[make_pair(x[i],y[j])];这种处理方法，如果没有想到-v[i-1][j-1]的话，就不会想到推出来vij也就没有后面的操作了。此外，在二维平面上这种只有两个轴向转移的思想也是很重要。确定了dp的一个转移的方向。最后，确定答案的一步也很有趣，由于离散化导致的不能确定m天的位置，所以只能再遍历所有的点然后取小于等于m天的那些点向m天转移的最大值。
wa点的话离散化忘记去重。。。。很尴尬的操作
[DP][思维] ZOJ3161 Damn Couples
题目最重要的是理解题意。。然后第二重要的是把原来的分散的点变成连续的：因为如果一开始的时候list上两个人就不相邻这时候最好就直接宣布了这个8g，因为这时候他们不会有任何一个人离开，这些操作之后也不用考虑了，这一步操作肯定的是最优的。
然后剩下的就是一块一块的被8g连起来的段，他们两两有一个8g，然后这时候可以用类似于矩阵链乘的算法，枚举第一次宣布的8g点，然后分成左右两块计算。max表示枚举断点取最大值，min表示顾客的想法：他们要让答案尽量小。
[比赛][递推][计数DP] 2018 ICPC 徐州网络赛 A Hard to prepare
比赛时候一直想推通式，然而并没有成功，和队友两个人用两种思路推出来两个公式。。。然后最后得知答案的通式是分奇偶性的，每个公式正好对一半，呵呵。。。。。
就题目本意来讲应该是dp。先把圆环展开为链，然后考虑一个满足题意的局面，这时候最后一位客人的面具与第一位客人的面具的关系决定了这条链是否能形成符合要求的环。如果一开始用两个状态分别表示最后一位与第一位冲突以及最后一位与第一位不冲突的两种情况，则会发现无法继续往后转移，因为从n位摆到n+1位的方法数是会受到前一位与第一位是否相同的影响的，因此需要再加一个状态信息，三个状态信息分别表示，最后一位与第一位相同，最后一位与第一位冲突，既不相等也不冲突，三种情况下的方案数，写出状态转移方程即可。
[DP][复杂度分析] Gym – 101485D Debugging
有趣的一道dp，让我想起了msc面试的时候问的扔杯子的问题。
首先，如果确定了对于长度为n的代码要写x个printf，那么这x个一定是尽量均匀分布（数学显然）才能使得最坏情况最好！因此，可以写出递推式：f(n)=min(f(ceil(1.0*n/i))+r+i*p);记忆化搜索暴力转移即可。
这个复杂度分析很数学：[n/i]的只有O(sqrt(n))种可能，每种可能的情况递归下去的话[n/ab]=[[n/a]/b],仍然是在那sqrt(n)种可能里面。所以总共有sqrt(n)个点会往下递归，每个递归点又最多有sqrt(n)次，相乘的话相当于O(n)； 继续阅读“[DP][复杂度分析] Gym – 101485D Debugging”
[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983
我上次wa两个小时是什么时候？？？妈的这个题格式。。。提示一个PE能死啊我去
直接暴力dp很好想但是复杂度爆炸，经过转换后可以把i和j分离开，然后j的那一部分就成了独立的只跟j有关的，这时候就可以把他当成一个新的量，然后求的时候就是在weight(j+1,i)<c的条件下（可以发现这其实是一个滑动的窗口）求出使得wav最小的j，就很像基本的dp了，只不过求最小j的时候用单调队列优化了。 继续阅读“[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983”