下面是我以前在我的Live Space的Blog上面写的一些ACM算法题目的解法，一次性贴出来供大家参考，也是对自己研究的一个记录。以后我做了新的题目会在CSDN Blog和我的Live Space Blog上面同时发布。
最近决定做一些ACM的题目来提高一下自己的算法的水平。N年(n>=6)没做这类型的题目了，手有点生疏了。网上有不少ACM的题目和Online Judge，UVa算是其中比较出名的一个。就从UVa开始做起吧。当时在学校就应该好好搞ACM的，可惜毕业之后才想起有ACM这回事 :(
Submit Program的几个注意事项：
输入输出直接从stdin/stdout，不用文件读写
可以接受一个输入立刻输出答案，不用全部记住答案然后一次性输出
最好用gcc/g++，避免Compile Error
注意IO结束条件是EOF还是其他的特殊值
这一道题看上去不难，直接一个一个硬算也可以得出答案。不过要快速得出答案自然需要用到Dynamic Programming，说白了就是要把中间结果记下来。用数组记当然最简单但是内存要求还是蛮大的，所以我先用map记了。算cycle number需要递归，我则是用的一个stack(vector)来去掉递归，先反复压栈直到答案已知，然后依次退栈计算。
程序写好了，提交上去居然是Compile Error? 看了一下网上的论坛，没找到什么有用的建议。试了一下#include老的.h的头文件依然Compile Error. 实在没有办法了，试着把int main(void)改成了int main(int argc, char *argv)，居然通过了。可是我的gcc并没有报错啊？
Compile Error好了，接下来居然是Wrong Answer。奇怪，我试过了不少答案应该是正确的阿。试着考虑一下i>j的case，还是Wrong Answer。上Forum看看，发现好多人接连试过n次都是Wrong Answer，幸好有人指点说i>j的时候i j不应该交换顺序，而是原样输出。比如100 1输出还是要输出100 1，不能图方便直接交换变成1 100。晕，题目明明没有说清楚这些额外条件阿，难道要我们自己猜？改好了之后又修了一个Bug，终于Accepted。不过时间就。。。 似乎比他们直接计算然后比较最大值来的还慢，可能是我为了节省内存用了map导致要不断进行查找导致速度偏慢。如果用数组应该会改善不少。BTW，我看到这个题结果排名前面的不少人居然CPU运行时间是0！？？ 就算再快也不可能快的这么离谱吧，会不会是他们预先把结果算好了然后直接输出了呢？
以后我会比较有规律的每个星期坚持做一些题目，然后把自己的解法Post出来。
开始101。这个题主要是模拟机器人移动方块，并不需要什么技巧。用一个list<int>作为stack来维护一堆积木的状态，用这样的一个vector来track每个位置的积木堆的状态。最后用一个pos的vector来track每个方块所在的位置。
刚开始的时候Wrong Answer，后来发现看错了题目要求，修改了一下便Accepted。这个题的通过率为25.7%，可能是题目要求比较容易出错导致的吧。
一个子问题是如何判断一个多维的盒子可以放在另外一个多维的盒子里面。其实只需要对各个维做一下排序然后依次顺序比较即可。
这个题目据我所知有两种方法：
方法1)
如果盒子a可以放置到盒子b中，则认为盒子a对应的节点a有一条边到盒子b对应的节点b。这样，问题转化为求All Pairs Longest Path。用动态规划可以解。
假定dist[i, j]是i到j的最大距离，则有
dist[i, j] = max { dist[i, r] + 1 | g[r, j] <> max }
计算Online Judge的Test Case用时0.088s
方法2)
比方法1快上不少。题目可以看成求严格递增的数字子序列(Longest Scattered Subsequence)。假定s[i] = 结束于i的子序列Ax1, Ax2, ... Axm, xm=i，于是有
s[i] = max { s[j] + 1 | A[j] < A[i] }
很典型的Bottom-Up Dynamic Programming.
计算Online Judge的Test Case用时0.010s，大概快9倍。
前几天就已经做完了，但是一直没有时间来写。这道题说白了无非就是求具有最大权值之积的最短环路。所以最根本的还是直接应用Floyd-Warshall算法，因为本题需要求最短的环路，所以在问题空间用两维的f[i][j]是不够的，需要用到三维: f[i][j][step]。step指path的长度。在Floyd-Warshall算法的三层循环之外还需要一层step的循环，公式如下：
f[i][j][step] = max { f[i][k][step-1] * f[k][j][1] | f[k][j][1] < max }
这次的程序和上次的都有Presentation Error。尝试了一下之后发现我在最后一个结果后面多Output了一个空格，去掉就Accept了。
前段时间研究过如何求最长连续公共子序列和最长连续子字符串，以前一个同学正好问起来，这里贴出来解法：
问题的关键还是如何定义子问题，
假设有：
Xm = x1 x2 x3 ... xm
Yn = y1 y2 y3 ... yn
1. 最长公共子序列(不必连续)
定义f(m, n)为Xm和Yn之间最长的子序列的长度
于是有f(m, 0) = f(0, m) = 0
如果xm != yn, 则f(m, n) = max{ f(m-1, n), f(m, n-1) }
如果xm = yn，则f(m, n) = f(m-1, n-1) + 1
问题归结于求f(m, n)。依照公式用Bottom-up Dynamic Programming可解
2. 最长子字符串(必须是连续的)
定义f(m, n)为Xm和Yn之间最长的子字符串的长度并且该子字符串结束于Xm & Yn。因为要求是连续的，所以定义f的时候多了一个要求字符串结束于Xm & Yn
于是有f(m, 0) = f(0, m) = 0
如果xm != yn, 则f(m, n) = 0
如果xm = yn, 则f(m, n) = f(m-1, n-1) + 1
因为最长字符串不一定结束于Xm / Yn末尾，所以这里必须求得所有可能的f(p, q) | 0 < p < m, 0 < q < n, 最大的f(p, q)就是解。依照公式用Bottom-up Dynamic Programming可解
其实是一个比较简单的题，有点奇怪为什么正确率那么低，可能大家忘了考虑负数了吧。Anyway，直接用递归下降法就可以解决。递归下降分析树结构的同时就相当于遍历了整棵树，因此无需在内存中把这棵树建立起来，而是在递归的时候同时累加，就可以知道是否存在这样的路径了。
今天解决了UVa 110 Meta-Loopless Sort。这道题的关键在于生成全排列的同时也需要确定如何进行比较可以得到此种全排列。生成全排列的方法有很多，但是有一种方法最适合此题：
假设我们获得了1~n的全排列，如何获得1~n+1的全排列？对于每个1~n的全排列x(1), x(2), ... x(n)，可以看作该排列中有n+1个空位，即，<slot>, x(1), <slot>, x(2), <slot>, ...., x(n), <slot>，于是把x(n+1)分别放入这n+1个空位可以得到从x(1), ... x(n)生成的所有1~n+1的全排列。同时，放入某个空位的同时也就决定了x(n+1)和每个元素的大小关系：
因为有x(1), x(2), ..., x(n)，因此有x(1) <= x(2) <= x(3) .... <= x(n)，则
x(n) < x(n+1), 则插入生成的排列为x(1), x(2), ..., x(n), x(n+1)
否则，如果x(n-1) < x(n+1), 则插入生成的排列为x(1), x(2), ..., x(n-1), x(n+1), x(n)
....
否则，（此时x(n+1) < x(1)），因此排列为x(n+1), x(1), ..., x(n)
通过这个关系就很容易生成整个if语句了。
此外，整个if语句比较像一颗树，所以采用类似深度优先的方式遍历生成此if语句是最自然的方法:
generate_if(n, sequence) // x(1), ..., x(n)=> insert n+1 into x(1), ... x(n)
{
for( i = 0; i <= n; ++i )
{
new_sequence = generate_new_sequence(sequence, i, n)
generate_if(n+1, new_sequence)
}
}
UVa - #112 - Longest Common Sub-Sequence
特意去找了这道题来做一下，巩固一下自己对此类算法的理解，顺便也试验了一下Bottom-up Dynamic Programming和Top-down Dynamic Programming的速度区别。一般来说，如果Bottom-Up Dynamic Programming没有计算很多没有用到的子问题的话，Bottom-Up Dynamic Programming要快于Top-Down的。这个题目比较搞的是，题目中完全没有提到字符串中居然会有空格......
UVa 507和108其实是相关的，507是基础，108是507基础上面的发挥。
ACM UVa 507 - Jill Rides Again
本质上来说，本题是一个Maximum Interval Sum问题，也就是求最大连续序列。一般的做法需要o(n^2)的时间，其实有一个简单的O(n)复杂度的解法：
从左到右逐步累加，记录每次累加之后的最大值，假如累加值<0，则将累加值清0，重新累加。当这个过程结束之后所记录的最大值就是最大的连续序列的累加值。因为只需要从左到右扫描一次，因此算法的复杂度为O(n)
直观来说，这样做把整个序列分为(A1, n1), (A2, n2)....(Am, nm)的序列。Ak是一串长度为w的序列a(1), a(2), ...a(w)其中a(1)+...+a(p) > 0对于任意0<p<=w。nk则是一个负数并且Ak+nk<0。这样，直观上来说，nk变成了各个序列的边界，每个序列不应该越过边界否则会导致序列的总和变小。因此最大的序列在A1, ... Am中（包括子序列），于是此算法可以得到最大值。
举例：
Seq=1, 2, -4, 9, -4, -7, 1, 4, 5, -2
Sum=1, 3, -1(清0), 9, 5, -2(清0), 1, 5, 10, 7
所以最大的连续序列为1, 4, 5，其和为10。
有了507的基础，108就比较好解决了。二维可以建立在一维的基础上面解决。任何一个n*m的Rectangle：
a11 a12 ... a1n
a21 a22 ... a2n
.....................
am1 am2 ... amn
可以看作一个一维的数组，其值为：( (a11+a12+...+a1n), (a21+a22+...+a2n), ..., (am1+am2+...+amn) )
于是求该Rectangle中最大n*k的Sub-Rectangle可以通过求该变换过的一维数组中的最大连续序列获得。注意求得的结果是n*k的。那么，对于二维数组中的每一行都可以有(1+n)*n/2种子序列，比如
a1,
a1, a2
a1, a2, ... an
a2,
a2, a3,
a2, a3, ... an
...
an-1, an
an
通过对每一个这样的子序列求和，正如上面所说，可以把2维问题转化为1维问题。
那么最终的算法的复杂度是多少呢？直觉上，求每行的i...j的子序列需要O(n^3)的复杂度（3层循环，一层i，一层j，一层从i+到j）再加上一维的从左往右的Scan共是O(n^4)。其实，求每行i..j的子序列不需要O(n^3)，注意到从i...j-1到i...j中间相差一个元素，因此可以通过利用上一次的计算的结果来累加的方式获得，所以只需要O(n^2)就可以做到。于是最后的复杂度为O(n^3)。
