去年校赛的时候感觉此题难的一批，，，昨天做polya练习题的时候做到了poj 2888去翻了下matrix67大神的十个利用矩阵乘法解决的经典题目中的第9题才恍然大悟。。。Oooooor2 做完这俩题再来看XDOJ的这个题已经是自然而然就可以搞出结果的了。
这个题的思想就是：把每一列3*1的小方格当成一个“珠子”，把他可能的8种情况当成“颜色”，然后这些颜色同时也代表状态，类似于poj2888的颜色相邻限制，这里的状态之间“能不能相邻”其实就是在状压dp里“能不能转移”的限制，不同状态之间的转移图如下（来自matrix67的那篇文章
紫书DP课后题最后一题了，也算是把这一部分做完了吧。
这个题，在uva上的数据太水了，导致很多网上的题解代码是错误的。在gym10128H这里会wa。这些题解大多是用一个简单的贪心策略处理分段，然后用区间dp处理分出来的段落。但是实际上分段也需要用一个dp，比如数据 1 2 4 3 1 2，用简单的贪心分段就会把4 3分到前面那一段，这样的出来结果是5（当把1 2 放进4 3里的时候4和3都要打开），但是如果把4 3分到后面的1 2里答案是4，是更优的解。
先讲简单的部分：分好段之后的区间dp。这个就是普通的区间dp $$dp(l,r)=min(dp(l,i)+dp(i+1,r)+cost(l,i,i+1,r)),i\in[l,r)$$其中 \[dp(l,r)\]表示
[l,r]之间的套娃组装成1个所需要的最小花费, 继续阅读“[区间DP][双DP][×] UVA 1579&Gym 10128H Matryoshka”
昨晚肝这一场是真的赔了，傻不拉几的C低级失误wa了一发，出完发现大家都会F然后跑去看了20min没头绪，折回去搞这个D，到最后也没过。。。感觉复杂度没错却一直tle，一直弄到两点受不了了睡觉去了，今早上课困得一批。
下午睡醒之后一直tle on test 27，给跪了好吧，疯狂卡常数真的有意思？最后把multiset改成priority_queue过了，真的服了，到目前为止52组数据吧，最狠的一组达到了2979ms，差21ms超时呵呵呵呵呵呵。。。
继续阅读“[CF][二分check][贪心][×] codeforces 1132D Stressful Training”
题目链接 https://cn.vjudge.net/problem/UVALive-4080
最短路基础题，有意思的部分在于最短路树这个东西的应用，还有对复杂度的正确估算（莽
看题目意思，基本上能确定枚举那条要去除的边然后算每种情况的c，但是如果直接这样的话复杂度会是n*m²*logn,就题目数据量而言基本上不可能过的。所以就要找其他方法来降低复杂度，考虑到，去掉一条边也许不会对以某些点为原点的到每个点的单源最短路产生影响（也就是不在这些点的最短路树上的边），可以试着预处理出来初始状态下每个边的影响到的点的集合，在枚举到这条边的时候只需要重新计算这些点的最短路而不用每次都计算所有点的最短路，这样的话可以把复杂度降低到n²mlogn。不得不吐槽一下这个解法，说实话感觉并没有降低多少就卡过了时限，数据刻意友好么。。。。比赛的话就算能想到这个也不一定敢写吧emmm
坑点是有重边，果然做图论最重要的是搞清楚图的类型。。。重边啊自环啊什么的真的烦,还有一开始小根堆写成大根堆了，又是wa又是t的 继续阅读“[蓝书][图论][最短路][坑] UVALive 4080 Walfare And Logistics”
题目链接 https://cn.vjudge.net/problem/UVA-1543
复习微机原理复习到吐，随便翻了个题写了写缓和一下脑子。。。。
一开始看题目给的信息总想着怎么能用到那个1/2sinα，然后就没什么头绪（后来发现给这公式只是用来计算三角形的）。后来开始想正常的dp套路，也就是以xx为结尾/开头的xx的大小，然后发现这个形状的大小不能只由一边来确定，所以加了一维表示另外一边的位置，最后整出来状态就是dp[i][j][k]表示在i到j之间选k个点能组成的最大的多边形大小 继续阅读“[DP][紫书][计算几何] UVA 1543 Telescope”
emmm第一感觉好像后缀数组之类的结构，但是这个每个元素是个整数，而字符串处理中每个元素都是一个长度为1的字符，，，所以很难把他等同于字符串来处理。但是直接理解的话，要求的话一定是找到一个排列，然后考虑他的每个子段，然后再在其他所有的排列中去找有没有这个子段，直接裸暴力的话n^3*10，肯定不行，但是想一下如果仅仅是考虑所有的子段就一定是不小于n^2的了，所以起码要在这里进行优化。然后由字符串的性质就可以知道一个长度为i的串如果满足要求的话，那么他的所有子串也都是满足要求的这些子串可以不用再计算了，发现了这个之后怎么去实施这个想法？考虑以每个下标i为开始的最长子串，这里如果用暴力的方法每次从i开始递增， 然后在与其他串判断，则当然仍然是n^3的，但是可以发现与其他串判断这个过程其实有很多重复的判断，假如已经知道了i到i+k个存在的话，判断第i+k+1个时候只需要把这一个数字去和其他的串中对应的数字比较是否全部相等就可以了，这样的话把复杂度降到了n^2*10，但是仍然不够，再考虑之前说的，枚举字段中的重复假设已经知道以i开始的到i+k个数字满足要求，那么在算以i+1开始的子段的时候，可以直接从第i+1+k+1个数字开始，也就是说中间的那些都不用再考虑了，因为这些信息已经在算第i个的时候计算过了。所需要保存的只有每个序列中数字i出现的位置而已。
嗯。。。。果然还是那句话，直接上组合数学搞不定的组合数学，要么打表要么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”
这个题确实是，自己想没有整出来。由于多考虑了一层，状态变得复杂了。
首先还是转化为有根树去做，然后考虑下自底向上的推法。因为这里多考虑一层，所以还需要考虑子节点的放置情况，也就是除了考虑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的变量，之后再用却没有正确赋值。。。
写这个是还是从今天那个C题目来的。看正解的时候发现了他用了一个很神奇的遍历质因子的方法，没有多余的操作，就是完全的遍历每一个质因子，只不过需要预先用线性筛处理出来1到n的每一个数字的最小质因子。感觉适用于需要分解多个数字质因子的情况但是我自己写的暴力sqrt(n)貌似也不慢多少就很迷。。。emmmmmm不管了先记下来再说。
