Hdu 5372 Segment Game

链接

Segment Game

题意

给定n个操作，操作有两种
0 b 插入一条[b,b+i] ，并输出被这条线段完全覆盖的线段条数，其中i表示这条线段是第i次插入
1 b 删除第b次插入的线段

01背包

有N件物品和一个容量为V的背包。第i件物品的费用为c[i]，价值为w[i]
求解将哪些物品装入背包可使价值总和最大？

暑假过半,好想天天睡懒觉…

基本思想

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题(阶段)，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解
与分治法最大的差别是：
适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的，即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解

Hdu 5344 MZL’s xor

链接

MZL’s xor

题意

给定n,m,z,l
$A_1=0,A_i=(A_{i−1}*m+z) \% l$
$求所有的 (A_i+A_j)(1≤i,j≤n) 异或的值$
如n=2 所求为：(A1+A1)^(A1+A2)^(A2+(A1)^(A2+A2)

考虑到第四场题目难度过大，加了两道水题
结果就只做出这两道水题

记忆化搜索

算法上依然是搜索的流程，但是搜索到的一些解，用动态规划的那种思想和模式作一些保存。一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。
这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。—[百度百科]

Sublime 功能强大，有很多快捷键
我觉得很方便的是多行编辑，同时修改多处