我的黄金时代

poj 2817 WordStack

先枚举预处理每两个单词之间的最大值。
然后易看出是要寻找一条遍历所有顶点一遍的最长路径，也即找到一条最长的Hamilton Path。(TSP问题)

状态为d[state][last]，代表遍历了state这些点，并且最后一个点为last时，最长的Hamilton Path。
状态方程为：d[state][last] = d[state-(1<<i)][i] + w[i][last] ( (i!=last) && ((1<<i)&state) )

poj 2677 Tour

TSP问题简化版，又称为bitonic tour。（参见算法导论习题15-1）

不妨将问题看作两个人同时从左向右走，并且两个人走过所有的点，且两人走过的点均不同，求两人走过的路径之和最短解。
状态为d[i][j]，代表了第一个人走到点i，第二个人走到点j，并且i>j，且i之前（包括i）的所有点均被走过，最短路径和。
状态方程为：
(1) i==j+1，d[i][j] = d[j][k] + w[k][i] ( 0<=k<j )
(2) i>j+1，d[i][j] = d[i-1][j] + w[i-1][i]

我想换一个两边都能出声的耳麦…

我想换双不漏风而且不漏雨的鞋子…

我想每天早上都有早饭吃…

我想把想读的书读完…

我想尽情的做有意义的research…

我还想更新blog，就像现在一样….

我想，我该去做些有意义的事情了…

“有意义的事就是好好活；好好活就是做很多很多有意义的事”

(1) n个有序集合求并
问题定义：设有n个有序数组，arr[i] ( 0<=i<n )，将这n个有序数组归并，得到一个有序数组。

解法[1]：
当n=2时，显然，我们只要线性扫描两个数组即可，复杂度O(size(arr[0]) + size(arr[1]))；
当n>2时，我们可以使用上述方法对有序数组两个两个的进行归并，最终得到一个有序数组。在总的归并过程中，每个元素被操作O(logn)次，因此，总的时间复杂度为O(mlogn)，m = sum(size(arr[i]))， 0<=i<n。

解法[2]：
不妨假设有序数组是按照非降序排序的。归并时，使用最小堆。首先将n个数组中的首元素压入最小堆。每次弹出最小堆中的堆顶元素，相当于得到了n个数组中当前处理位置中最小的元素，然后将弹出元素所在数组中的下一个元素压入最小堆。每个元素在最小堆上均被插入和弹出一次，O(logn)，所以总的时间复杂度为O(mlogn)，m = sum(size(arr[i]))， 0<=i<n。

(2) n个有序集合求交
问题定义：设有n个有序数组，arr[i] ( 0<=i<n )，将这n个有序数组求交，得到一个有序数组。

解法：
对所有数组线性扫描一遍即可。不妨设有序数组是按照非降序排序的。
设min为所有数组当前被扫描位置的最小值，max为最大。若min==max，则将此值加入新数组。若min!=max，则对每个数组从当前位置起扫描，直至找到第一个大于等于min的数，如此循环。
时间复杂度为，O(m)，m = sum(size(arr[i]))， 0<=i<n。

伪码如下：

	for each arr
		pos[i] = -1

	min = max = 0
	end = false
	while end == false
		if min == max
			for each arr
				++pos[i]
				if pos[i] >= size(arr[i])
					end = true
					break
		else if min != max
			min = max
			for each arr
			while arr[i][pos[i]] < min
				++pos[i]
				if pos[i] >= size(arr[i])
					end = true
					break
			if arr[i][pos[i]] > max
				max = arr[i][pos[i]]
		while end == false
			if min == max
			newarr.add(min)