摘要: 经典的状态压缩DP。f[i][j]表示第i行，方格排布为二进制数j（第k位上为1表示凸出一个格子，为0表示不凸出）的方案数。用DFS进行状态转移。
如果行数比较多的话，可以用矩阵乘法优化。因为每行的状态转移都是相同的。设烈数为m，行数为n，可以做到O(2^(3m)logn)。

  阅读全文      摘要: 经典的TSP问题变种。状态为f[i][j][k]，表示经过二进制数i所指的哈密顿路（第bi位为1表示经过该点，为0表示不经过该点），倒数第二个点为j，最后一个点为k。.value表示最大权值，.num表示能走出最大权值的路径数。若图中k到p有边，f[i][j][k]则转移到f[i'][k][p]。i' == i | (1 << p)。

  阅读全文      摘要:

  阅读全文      摘要: int f[i][j]表示第i个字符到第j个字符需要添加的最少括号数。string ans[i][j] 表示第i个字符到第j个字符按照最优方案添加括号后的串。状态转移：1.f[i][j]由f[i + 1][j - 1]转移来（通过两端添括号() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]转移来（通过串合并）。答案是ans[0][len - 1]。

  阅读全文      摘要: 枚举矩形的上边和下边，花费O(n^2)，把问题转化成一维的最大M子段和，做一个O(n)的DP。
  阅读全文      摘要: pku 部分动态规划题目列表

  阅读全文      摘要: 题目给出 n 个矩形，要求它们的面积并。具体做法是离散化。先把 2n 个 x 坐标排序去重，然后再把所有水平线段（要记录是矩形上边还是下边）按 y 坐标排序。最后对于每一小段区间 (x[i], x[i + 1]) 扫描所有的水平线段，求出这些水平线段在小区间内覆盖的面积。总的时间复杂度是 O(n^2)。利用线段树，可以优化到 O(nlogn)。

  阅读全文      摘要: 求多边形的核。用半平面交算法。

  阅读全文      摘要: 强烈推荐此题！
先考察一下这个问题的性质。
性质1：任何一个圆都覆盖了一个闭区域。
性质2：对于任意一个点，覆盖它的最上面的那个圆，一定是可见的。
性质3：如果一个圆不可见（它被完全覆盖），那么它的边界是被完全覆盖的。
性质4：n个圆最多有2(n-1)^2个交点，这些交点把n个圆分成最多2(n-1)^2条小圆弧。
性质5：对于每个小圆弧，要么它全被覆盖，要么它全不被覆盖。
根据性质1和性质2，问题转化为恰当地找出一些点，对于每个点，把覆盖它的最上面的圆标记为可见。
根据性质3，这些点一定在所有圆的边界集合内。
根据性质5，所有小圆弧构成边界集合。每个小圆弧上只要任意取一个点就能代表整个小圆弧（边界）。不妨取中点。
至此得到算法：取所有小圆弧的中点，对每个点找到覆盖它的最上面的圆。
根据性质4，最多取2(n-1)^2个点。对每个点找到覆盖它的最上面的圆，需要O(n)次运算。总复杂度是O(n^3)。

  阅读全文      摘要: Bless GCC!

  阅读全文