題意：
給定一條 ‘a’ 及 ‘b’ 的 string
長度為 N (≤ 300)
現在可重覆以下操作：
把長度為 3 的 substring “xyx” 轉換成 “y”（其中 x, y = ‘a’, ‘b’）
問 string 最多可以縮至多短
樣例：
“abaaaaaba” → “bab” → “a”
答案 = 1
算法：
O(N3)動態規劃
2010年7月3日星期六
SPOJ 4532 String reduction
給定一條 ‘a’ 及 ‘b’ 的 string
長度為 N (≤ 300)
現在可重覆以下操作：
把長度為 3 的 substring “xyx” 轉換成 “y”（其中 x, y = ‘a’, ‘b’）
問 string 最多可以縮至多短
“abaaaaaba” → “bab” → “a”
答案 = 1
O(N3)動態規劃
2010年6月19日星期六
PKU 1952 BUY LOW, BUY LOWER
Problem Statement:
給定陣列 A[N], 其中 1 ≤ A[i] ≤ 215-1
求最長嚴格下降序列 (Strictly Longest Decreasing Subsequence) 的長度及方法數
當序列元素完全相同，則兩個方法視為一樣（見樣例）
Sample Input:
Sample Output:
題目最難之處就是要避免重計
其中一個有效方法就是以元素的值作為狀態
為此，自己的第一個 AC Submission 就加入了三項預處理...
寫的很累贅...
後來 Google 了一下
發現自己沒有用到一項已經發現的 Observation：
給定陣列 A[N], 其中 1 ≤ A[i] ≤ 215-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：
2010年6月16日星期三
[進階DP] 基於連通性狀態壓縮的動態規劃問題
看完 男人八題 的 題C：Tony's Tour 以後
[I like the title: "做男人不容易系列:是男人就过8题--LouTiancheng题"]
即時想起：
ICPC World Fianls 2010 - Problem I : Robots on Ice
連結：
1) 《基于连通性状态压缩的动态规划问题》 By Cdq（陈丹琦）
2) 【动态规划】Ural1519 Formula 1 - By ccy1991911
這是Google 返回的 Blog 文...
感覺寫的挺用心（未詳閱）
3) 【专辑】插头DP
NotOnlySuccess 寫的
插個花：
雖然自己都幾鐘意之前呢個黑底白字既 theme
而且感覺亦幾 Professional =v=
不過望落去時對眼真係有啲辛苦... 所以都係轉番白底黑字好啲
呀... 另外一個原因係 LaTeX 冇黑底白字（好似係）
呃... 暫時黎講個 blog 都仲係寫得冇乜系統
究竟寫 Technical Term 用中定英好呢？
白話文定書面語好呢？
[I like the title: "做男人不容易系列:是男人就过8题--LouTiancheng题"]
即時想起：
ICPC World Fianls 2010 - Problem I : Robots on Ice
連結：
1) 《基于连通性状态压缩的动态规划问题》 By Cdq（陈丹琦）
- 插頭 DP
- 括號表示法（好似係）
- Hamiltonian Path
2) 【动态规划】Ural1519 Formula 1 - By ccy1991911
這是Google 返回的 Blog 文...
感覺寫的挺用心（未詳閱）
3) 【专辑】插头DP
NotOnlySuccess 寫的
插個花：
雖然自己都幾鐘意之前呢個黑底白字既 theme
而且感覺亦幾 Professional =v=
不過望落去時對眼真係有啲辛苦... 所以都係轉番白底黑字好啲
呀... 另外一個原因係 LaTeX 冇黑底白字（好似係）
呃... 暫時黎講個 blog 都仲係寫得冇乜系統
究竟寫 Technical Term 用中定英好呢？
白話文定書面語好呢？
2010年2月10日星期三
ICPC 4455 Suffix-Replacement Grammars
ICPC 4455 Suffix-Replacement Grammars
[World Finals 2009 - Problem K]
題意：
現給定 N (<=100) 項規則，每項
形式為： X→Y（其中 X 和 Y 等長）
意義是：若字串的後綴為 X，則可花費用 1 ，將後綴替換成 Y。
求由字串 S 轉換至 T 最短路*。（其中 S 和 T 等長）
所有字串長度最多為 20。
[* 即 最小費用，使用 "最短路" 此詞是因為描術更直觀]
樣例：
規則：
BC → CD
BC → CA
BCD → CCZ
A → C
S = BBA
T = CCZ
BBA
→ BBC (應用 "A → C")
→ BCD (應用 "BC → CD")
→ CCZ (應用 "BCD → CCZ")
Answer: 3
[World Finals 2009 - Problem K]
題意：
現給定 N (<=100) 項規則，每項
形式為： X→Y（其中 X 和 Y 等長）
意義是：若字串的後綴為 X，則可花費用 1 ，將後綴替換成 Y。
求由字串 S 轉換至 T 最短路*。（其中 S 和 T 等長）
所有字串長度最多為 20。
[* 即 最小費用，使用 "最短路" 此詞是因為描術更直觀]
樣例：
規則：
BC → CD
BC → CA
BCD → CCZ
A → C
S = BBA
T = CCZ
BBA
→ BBC (應用 "A → C")
→ BCD (應用 "BC → CD")
→ CCZ (應用 "BCD → CCZ")
Answer: 3
訂閱：
文章 (Atom)