下面是我以前在我的Live Space的Blog上面写的一些ACM算法题目的解法，一次性贴出来供大家参考，也是对自己研究的一个记录。以后我做了新的题目会在CSDN Blog和我的Live Space Blog上面同时发布。
- 输入输出直接从stdin/stdout，不用文件读写
- 可以接受一个输入立刻输出答案，不用全部记住答案然后一次性输出
- 最好用gcc/g++，避免Compile Error
- 注意IO结束条件是EOF还是其他的特殊值
一个子问题是如何判断一个多维的盒子可以放在另外一个多维的盒子里面。其实只需要对各个维做一下排序然后依次顺序比较即可。
方法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 }
方法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.
前几天就已经做完了，但是一直没有时间来写。这道题说白了无非就是求具有最大权值之积的最短环路。所以最根本的还是直接应用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了。
其实是一个比较简单的题，有点奇怪为什么正确率那么低，可能大家忘了考虑负数了吧。Anyway，直接用递归下降法就可以解决。递归下降分析树结构的同时就相当于遍历了整棵树，因此无需在内存中把这棵树建立起来，而是在递归的时候同时累加，就可以知道是否存在这样的路径了。
UVa - #10405 - Longest Common Sub-Sequence
特意去找了这道题来做一下，巩固一下自己对此类算法的理解，顺便也试验了一下Bottom-up Dynamic Programming和Top-down Dynamic Programming的速度区别。一般来说，如果Bottom-Up Dynamic Programming没有计算很多没有用到的子问题的话，Bottom-Up Dynamic Programming要快于Top-Down的。这个题目比较搞的是，题目中完全没有提到字符串中居然会有空格......