HDU 1257 - Zui Shao Lan Jie Xi Tong
Problem : Given a sequence. Find the minimum number of subsequences s.t. each subsequence is a non-increasing sequence, and the union of them is the original sequence.
Solution :
1) Problem Transform: Any strategy of original problem can be transformed like this: There are n elements initially equals inf. For each element of sequence in order, choose one of the constructed element which has larger value than the element from sequence, then change former to latter. The answer of strategy is the number of constructed elements which has the value doesn't equal inf.
proof:
-> : For any strategy of original problem. Check the elements in original sequence order, if current element S[j] is in the i-th subsequence, change the i-th constructed element to S[j]. Obviously, before changing, the i-th element will not smaller than S[j], since its last change is by the sequence element S[k] (k<j), which is in the same subsequence with S[j], and comes before S[j]. At last, there are 'answer of strategy' constructed elements which is nor equal to inf.
<- : For any strategy of transformed problem. When i-th constructed element is changed to S[j], put S[j] to i-th subsequence. Since the constructed element can be changed, its previous value S[k] must be not smaller than S[j], thus add S[j] to tail of i-th subsequence is valid (Before add, the tail of i-th subsequence is S[k]).
[]

2) Algorithm : each time find the smallest constructed element that is not smaller than S[i], and change it to S[i]. It's the best answer.
proof:
	A. Let a[i] to be the list of constructed elements in order from smaller to larger when S[i] is processed in algorithm. b[i] is any other algorithm's order list. It always holds a[i][j]>=b[i][j].
	proof: (reduction)
	1. when i=0, all the elements is inf, the theory holds.
	2. when i=k holds the theory, now i=k+1.
	a[k+1] can be get by finding the smallest j s.t. a[k][j]>=S[i], deleting it, and insert S[i] into it. b[k+1] can be get by finding the element j' s.t. b[k][j']>=S[i], deleting it, and insert S[i] into it.
		a. Since a[k][j']>=b[k][j']>=S[i], j<=j'.
		b. After deleting, denote the remaining list to be a'[k] and b'[k], it holds a'[k]>=b'[k]. (See the note)
		c. Since a'[k] and b'[k] also holds the theory, by inserting the same element S[i], the resulting list a[k+1] and b[k+1] also holds the theory. (See the note).
	By c, when i=k+1 the theory holds.
	[]

	B. Since a[n] and b[n] holds a[n][j]>=b[n][j] for all j, Thus the number of non-inf in a[n] must no more than that of b[n].
[]