DP
SRM 195 DIV2 FanFailure
算滿水的題目，不過題意讀得很累
Copy
/\*
\* GCA : "Computer is artificial subject absolutely,Math is God"
\*/
#include <iostream>
#include…
Codeforces Round #178 (Div. 2) B - Shaass and Bookshelf
DP dp [i] i 表示厚度，而 dp [i] 的值是這個厚度當中 寬度最大的為多少
之後再用總數去扣掉即可
貌似有 greedy 解法，分成厚度 1 跟 2 具體內容要參考其他 blog
Copy
/\*
\* GCA : Where is the Dp,there…
Codeforces Round #208 (Div. 2) D. Dima and Hares
只可意會不可言傳的 DP ...
附上官方題解Tutorial
D. Dima and Hares
Let's look at the first hare: we chose them befoe second, or after. If it is chosen after…
Codeforces Round #114 (Div. 1) B. Wizards and Huge Prize
難題....DP 參考了 turiol 跟解題報告 這題給了 n,l,k
那麼我們就用這三個來做 DP 狀態轉移
dp[i][j][m] win j of the first i days and get total bag Probability
所以
如果拿到包包的話
dp…
Codeforces Round #201 (Div. 2) D. Lucky Common Subsequence
求出最長子序列，且不包含一個子字串 DP 難題，要在 LCS 上面多開一維的空間
用來記錄病毒字串的生長，所以需要用 KMP
首次深入學習了
Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC…
uva 11780
比較簡單的 DP 題，為了少掉浮點數，把 DP 全部 * 10 Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC:::…
uva 11003
誰能告訴我 DP 到底是誰想出來的 真的有夠噁爛 dp(i, j) = min{dp(i-1, j), dp(i-1, j-1)+w[i]}
記得有條件
Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC…
uva 11022
直接全暴力搜索 + 記憶化表單 數據感覺好像很小，過得很快
Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC:::::…
uva 10818
這題非常的複雜 + 麻煩，需要用到 BFS+Hamilton Path+DP Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G…
uva 11240
利用 LIS 特性去做就可以了 只是只要更新目前的就可以了
Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC:::::…
uva 11052
把滿足條件的由上到下所有組合最佳化一次 也就是 DP
EX
index year month
0 0 1
1 0 3
2 1 2
3 1 11
4 1 12
5 2 5
6 2 8
7 3 4
dp[0]=1
dp[1]=dp[0]+1
dp [2]=dp [1]+1 (dp…
uva 10453
DP 作法，還要通路復原 dp[i][j]= if(i==j) dp[i+1][j-1]
else min{dp[i][j-1],dp[i+1][j]}+1
Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC…
uva 10898
利用 DP 紀錄表單進行遞迴即可 Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC::::::::::::C…
uva 10118
利用 DP 做記憶化搜索即可 Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC::::::::::::C…
uva 10532
想了半天原來是 DP 問題... Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC::::::::::::C…
uva 10593
兩次 DP 即可 Copy
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC::::::::::::C…
uva 10516
這題本質上是 DP 為了加速所以寫了大數的快速冪
dp [i]=dp [i-1]^n+1 感謝網路博客 http://www.cnblogs.com/staginner/archive/2011/12/17/2290920.html
每次都有一個頭然後 n 個連出去的節點
所以…
uva 709
dp [i] 表示某行到第 i 個單字結束的時候最小的 badness dp[i] = min{dp[i-1]+500,dp[j]+badness
(參考至http://www.cnblogs.com/staginner/archive/2011/12/07/2279059…