这个题有很多做法，目前先用二分+KMP过了，二分的原理是如果最大字串存在那么这个最大字串的字串也一定满足要求。难得1Y，明天用后缀数组尝试一下来填坑。。
[01分数规划][二分][精度][坑] POJ2976 Dropping tests
二分答案倒是容易想到，实现的话需要排序后贪心，但是坑在精度上
我用了printf(“%.0f\n”,ans); WA cout<<(int )(ans+0.5)<<endl; AC 就很玄学。。。。学到了学到了
继续阅读“[01分数规划][二分][精度][坑] POJ2976 Dropping tests”
[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning
思路全在论文里，实现的话费了点功夫。。感觉写这种复杂一点的题，最好还是先把需要用到的变量都写出来，需要的操作都列出来，不然反复修改会浪费很多时间。
需要注意的错误只发现了一个就是在枚举加度的时候可能会出现没边可删的情况（我也不知道为什么），然后这时候我的代码就开始跑环。。因为每次都会新加入一条边，不删边的话必定在树上形成环。后来的策略是一旦当前的操作不再使得生成树变小，那就直接break，因为显然他之后也不会再变小，而且可能之后会出现跑环，而这之前我的代码都是正确的，这样既可以剪枝又可以避免坑。。。 继续阅读“[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning”
[对抗搜索][剪枝][建模转化][模板] POJ 1085
minimax搜索+α-β剪枝优化模板题。
第一个需要处理的就是把状态全部转化成二进制形式，包括三角形，边，棋盘，等等。转化好了之后就可以用minimax搜索了。在一开始的时候边读入边改变局面和cnta，cntb这两个分别代表a和b的得分，这个题有需要注意的一点就是如果一方得分了那么他是可以继续下一轮的，所以每次都要判断走向下一个局面的时候是不是得分。注意α是max层的最大值的最小边界，β是min层的最小值的最大边界，这里对一方操作之后发现不再满足α<=β，其实是跟父节点的另一方作对比的，一旦不满足即说明当前节点不再有利用价值，直接把这个越界的值返回父节点即可（因为父节点还是要更新状态的）这里并没有要求算出具体得分，所以用-1和1 来表示输赢即可，在每一层里加上cnt与5的关系判别也可以做到剪枝的作用。
[DP][线段树][离散化][细节][坑] XDOJ 1324
离散化写挫了就wa了n发。。
先按照右端点排序，设dp[i]为铺满1到i的最小价值，注意是铺满，那么就可以在这里更新dp[r[i]]=min(dp[j])+v[i] l[i]<=j<=r[i]，注意这里有一个-1，对于左端点来说，因为如果两个线段相邻二不相交，比如(1,2)(3,4)，这样其实也是可以的。这里的话，如果直接把端点离散化，就会导致后面的操作很复杂，因为要考虑相邻中间有没有空（我也是这么错的），所以不如直接在一开始读入左端点的时候就给他-1，这样之后就不用什么多余的操作了，直接每次线段树查询最小值即可。 继续阅读“[DP][线段树][离散化][细节][坑] XDOJ 1324”