ACM UVa 算法题100, 101, 103, 104, 112, 110, 112, 507, 108解法

1. 输入输出直接从stdin/stdout，不用文件读写
2. 可以接受一个输入立刻输出答案，不用全部记住答案然后一次性输出
3. 最好用gcc/g++，避免Compile Error
4. 注意IO结束条件是EOF还是其他的特殊值

UVa - #104 - Arbitrage

前几天就已经做完了，但是一直没有时间来写。这道题说白了无非就是求具有最大权值之积的最短环路。所以最根本的还是直接应用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可解

今天解决了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。

ACM UVa 108 - Maximum Sum

有了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)。