HDU 3208 Integer's Power

在 HDU OJ 看 problem title 隨便挑的一題...
據 AC rate 判定這題值得一做

---

題意：

對於正整數 x = b^e，其中 b、e 為正整數
定義 x (≥ 2) 的 integer power 為 e 的最大可能值
（81 的 integer power 是 4，不是 2）

給定正整數 2 ≤ A ≤ B ≤ 10¹⁸
求 [A, B] 區間內所有正整數的 integer power 的總和

---

分析：

稍為簡化問題：
令 f(Y) := [1, Y] 區間所有正整數的 integer power 總和
則答案 = f(B) - f(A - 1)

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：

[進階DP] 基於連通性狀態壓縮的動態規劃問題

看完 男人八題 的 題C：Tony's Tour 以後
[I like the title: "做男人不容易系列:是男人就过8题--LouTiancheng题"]

即時想起：
ICPC World Fianls 2010 - Problem I : Robots on Ice

---

連結：
1) 《基于连通性状态压缩的动态规划问题》 By Cdq（陈丹琦）

• 插頭 DP
• 括號表示法（好似係）
• Hamiltonian Path
  

似乎就係 exactly 老細想我地學既野...?

2) 【动态规划】Ural1519 Formula 1 - By ccy1991911
這是Google 返回的 Blog 文...
感覺寫的挺用心（未詳閱）

3) 【专辑】插头DP
NotOnlySuccess 寫的

---

插個花：
雖然自己都幾鐘意之前呢個黑底白字既 theme
而且感覺亦幾 Professional =v=
不過望落去時對眼真係有啲辛苦... 所以都係轉番白底黑字好啲

呀... 另外一個原因係 LaTeX 冇黑底白字（好似係）

呃... 暫時黎講個 blog 都仲係寫得冇乜系統
究竟寫 Technical Term 用中定英好呢？
白話文定書面語好呢？