PKU 1952 BUY LOW, BUY LOWER

Problem Statement:
給定陣列 A[N], 其中 1 ≤ A[i] ≤ 2¹⁵-1
求最長嚴格下降序列 (Strictly Longest Decreasing Subsequence) 的長度及方法數

當序列元素完全相同，則兩個方法視為一樣（見樣例）

---

Sample Input:

12
68 69 54 64 68 64 70 67 78 62 98 87
1   1  2  2  2  3  1  3  1  4  1  2 // Explaination
69       68 64          62
69       68       67    62

Sample Output:

4 2 

---

題目最難之處就是要避免重計
其中一個有效方法就是以元素的值作為狀態

為此，自己的第一個 AC Submission 就加入了三項預處理...
寫的很累贅...

後來 Google 了一下
發現自己沒有用到一項已經發現的 Observation：

若 A[i] = A[j] 及 i ≤ j，則有 LDS[i] ≤ LDS[j]

其中 LDS[i] := 截至且包含 A[i] 的 最長嚴格下降序列的長度

這樣一來，只要在更新 LDS[i] 的值時
由 j := i-1 至 0 掃描
只使用未用過的數值更新答案
（元素取值範圍小 ⇒ 只要 bool vis[2¹⁵-1] 紀錄就足夠矣）
就不會重計了！

---

Pseudo Code:
For i := 0 to N
　LDS[i] := 1
　CNT[i] := 1 // Number of LDS's
EndFor
For i := 0 to N
　For j := i-1 to 0
　　If A[j] is used in this i-iteration
　　　Continue
　　ElseIf A[j] > A[i]
　　　Update LDS[j], CNT[j] accordingly...
　　　Mark A[j] as used
　　EndIf
　EndFor
EndFor

---

Summary:
Time Complexity: O(N²)

---

Subtlety:
另外一些使代碼更精簡的方法：

1) 在陣列 A[N] 的末端添加一個 "0" 以及把 LDS[i] 的值起始為 0
列印答案： LDS[N-1] + " " + CNT[N-1]

好處

• 最後沒需要在 LDS[] 陣列中，查找所有 Maximal Element
• 在聲明 LDS[] 時打 = {0} 便行
• 節省一個起始 (LDS[i] = 1) 用的 For-循環

2) 一個由 CTLi 引入的... 有關 Set Visited 的方法...
不說了

3) 利用 樹狀數組 (Binary Indexed Tree) 可以 加快至 O(N lg N)
參考 Waihon 的 Blog