好久不写了啊，最近打算重新启用这个blog。就先写这个题目吧，满经典的。
【题目大意】
　　m * n的区域内，每个整数坐标都有整点，问以这些整点为端点能够形成多少个三角形。（0 < m, n <= 1000）

【题目分析】
　　这个题目乍一看挺简单的，但是想做对还是要仔细的思考下的。补集转化的思想，求出所有共线的三元组，然后用总数减掉就是答案了，关键就是如何求共线三元组。x坐标相同和y坐标相同的比较好计算，在一条斜线的就不好算了，画个图发现，即使斜率相同的线，经过的格点数可能各不相同。思路当然还是枚举y / x（不同的y / x确定了不同的矩形区域），之后如何有效的计算，我采用的方法可能有些麻烦，有点类容斥的方法。以斜率为a / b为例，(a, b) = g，那么m * n的区域内一定有(m - a + 1) * (n - b + 1)个那么大的矩形，这样的矩形经过的格点数是(g + 1)；然后因为同等斜率小一点的矩形(a - a / g, b - b / g)也是存在的，个数同样可以统计出来，但是有些大矩形包括了，要去掉；因此就采用这种思想，先求出大矩形的个数，然后依次往下减，就可以避免重复计数了。虽然这样复杂度有点高，不过极限数据还是比较快的跑出来了。
　　说的可能不太清楚，具体代码如下：

这个题目去年就过了，用得是状态压缩dp，不过没用dfs预处理，当时做得不是很明白，还是参考网上的一个代码做的。
现在重新做了一下这个题目，请教了icecream，学会了一个很简练的做法，而且比较好理解还好写。
首先还是状态的表示，用0表示没有放木块，用1表示放了木块。此外，对于一个横放的木块，对应的两位都用1表示；对于一个竖放的木块，第一行用1表示，第二行用0表示。这只是一种设状态的方式，当然还有别的设法，但是这种方法在接下来就会发现优点。

状态表示完就要处理转移了，如何判断一个转移是否合法比较难办，用一个dfs却可以简洁的解决这个问题。
对于上一行到下一行的转移，规定上一行一定填满，这样有三种方式：
    dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
    dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
    dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
第一种上面是1，那么下面一定是0，表示是一个竖放的木块。
第二种上面是0，就是说这个位置一定是一个竖放木块的下半截，那么下一行肯定是要另起一行了，放一个竖放或者横放的木块都必须是1。
第三种相当于上下两行各放一个横木块。
实现的时候我用了一个vector记录每个状态所有可行的转移，这样在dp的时候可以加快一些效率。

还有一个问题需要考虑，那就是初值和最终的结果。如果寻找合法状态，依然比较麻烦，假设共有n行，可以分别在这n行上下新加两行。下面一行都是1，由于第n行肯定要填满，这样新加的全1的行就相当于顶住了第n行使其没有凸出（有凸出那么第n+1行有0），而通过第n行到第n+1行转移保留了所有合法状态；同理最上面加的那行保证第一行没有凸出。最后第n+1行对应全1的状态就是最终的结果了。通过新加行巧妙地解决了初值和终值。

实现的时候也需要注意一下，在TSP问题中，外层循环是状态，内层是点，之所以这样写因为在枚举点的时候，可能会从比当前编号大的点转移，但是由于无论怎样转移过来的状态肯定比当前状态小（去掉了1），所以先从小到大枚举状态就保证转移过来的状态一定是算过的。而这个题目里面正好反过来，因为状态可能从比当前状态大的状态转移过来，而行数肯定是从编号小的行转移，因此先枚举行就能保证转移过来的状态一定是更新过的。

【题目大意】
　　定义两个三元组I(xi, yi, zi)和J(xj, yj, zj)，他们的差为D(I, J) = max{xi - xj, yi - yj, zi - zj} - min{xi - xj, yi - yj, zi - zj}，给定n个三元组（n <= 200000），求任意两个三元组的差的和。

【题目分析】
　　数据范围非常大，枚举必然不可，需要数学方法。这个题目巧妙之处在于，模型经过了层层的包装，要想一下子有想法还真不容易。既然不能枚举了，这个max和min操作就不好办了，应该设法去掉。max{a, b, c} - min{a, b, c} = |a - b| + |b - c| + | c - a| / 2，这个公式应该不难想到，但是这只是第一步，因为引进了绝对值，依然不好做。可以先算出分子，最后再除2。接下来需要一个等价变换，以a - b为例，a - b = xi - xj - yi + yj = (xi - yi) - (xj - yj)，同理把b - c、c - a都写成这种形式。这一步变换看似作用不大，但是假设我们算出所有的xi - yi之后（i = 0... n - 1），将其排序，会发现，对于第i个xi - yi，它前面的都比它小，后面的都比它大。而实际上，由于求任意两个三元组的差，肯定xi - yi会和任意的xj - yj都作差的，加了绝对值后，它对最后的结果就会贡献i个(xi - yi)，n - i - 1个-(xi - yi)。同样的方法算出所有的(yi - zi)和(zi - xi)，结果就能够求出来了。算法复杂度O(n * logn)。

【题目总结】
　　这是一道不错的题目，首先考察了公式的变形，需要改写max - min操作，之后的等价变换和排序的思想都非常值得借鉴。
题目代码：

　　题目大意是给定n个点的坐标（n <= 10000），问把这些点移动到一横行并且一个挨着一个（具体位置任意）的最少移动步数（其中每次只能向上下左右移动一个坐标）。
　　这个题目体现了转化的思想。首先考虑这样的问题：一个数轴上有n个坐标，问把这n个坐标移动到一个点上最少移动步数，其中每次移动一个格子。根据中位数的定义，把所有坐标排序后第n / 2个坐标是中位数，把所有坐标移动到这上面移动次数最小。证明很容易想到，因为如果不这样的话，把目标坐标往左平移还是往右平移，势必造成左半部的坐标集体变化1，右半部的坐标也集体变化1，如果左右半部坐标的个数不同，那么显然就不是最优的了。
　　接下来考虑题目，题目中x和y的移动是孤立的，可以分开讨论。y的移动方法和上面讨论的情况一样，现在考虑x的移动。x的移动要求最终是一个挨着一个的，x排好序之后，假设最终所有点以x0为左端点依次排开，对应的点分别为x0, x1...那么问题的答案就等于把这n个坐标依次对应的挪到x0到xn-1上的步数。如果我们把这n个目标点分别都移动到x0上，那么问题就转化成了中位数问题了。考虑把xi移动到x0上，要花费i步，为了保证问题是等价变换的，应该把xi在原坐标中对应的xi'也相应的向左移动i步，这样xi'移动到xi的代价就是不变的。设xi'左移i步后的新位置是xi''，那么问题就转化成：把x0''到xn-1''这n个点移动到一个坐标的最小步数，用中位数的方法就可以做出来了。
　　这个题目的巧妙之处在于把一个未知问题转化成一个已知问题。转化的思想在数学中用的很多，应该多多练习。

题目代码：

　　给定n个数求这n个数划分成互不相交的m段的最大m子段和。
　　经典的动态规划优化的问题。设f(i, j)表示前i个数划分成j段，且包括第i个数的最大m子段和，那么有dp方程：
　　　　f(i, j) = max { f(i - 1, j) + v[i], max {f(k, j - 1) + v[i]}(k = j - 1 ... i - 1) }
　　也就是说第i个数要么自己划到第j段，要么和前一个数一起划到第j段里面，转移是O(n)的，总复杂度O(n * n * m)。
　　可以引入一个辅助数组来优化转移。设g(i, j)表示前i个数划分成j段的最大子段和（注意第i个数未必在j段里面），那么递推关系如下：
　　　　g(i, j) = max{g(i - 1, j), f(i, j)}，分是否加入第i个数来转移
　　这样f的递推关系就变成：
　　　　f(i, j) = max{f(i - 1, j), g(i - 1, j - 1)} + v[i]，转移变成了O(1)
　　这样最后的结果就是g[n][m]，通过引入辅助数组巧妙的优化了转移。实现的时候可以用一维数组，速度很快。

附HDU 1024题目代码：