zju 1520 Duty Free Shop
摘要: 經(jīng)典背包，記錄路徑，放得下就行。
閱讀全文
zju 1503 One Person "The Price is Right"
摘要: 1503 估價游戲，一個決策為背景的 DP，當前剩下 i 次機會和 j 條命，最優(yōu)的策略可以覆蓋 DP[i][j] 范圍內(nèi)的所有情況，那么DP[0][j] = 0, DP[i][0] = i, DP[i][j] = DP[i-1][j-1] + 1 + DP[i-1][j]。
閱讀全文
zju 2975 Kinds of Fuwas
摘要: 沒看出來有dp的思想，還是同學(xué)教的~
閱讀全文
hdu 1500 Chopsticks
摘要: 參考了下別人的代碼，dp真是千變?nèi)f化啊！
這與搬寢室還是有很大不同的，要倒過來做；
dp[物品組數(shù)][物品個數(shù)](I為I副筷子，J為總共筷子)
現(xiàn)在轉(zhuǎn)入正題,這個題目要求每一組有3個筷子,前2個的差的平方最小,
首先和前面題目一樣先排序?qū)Π?顯然從大到小排(因為這樣完全可以轉(zhuǎn)化成搬寢室 那個一樣的思想)
比如取第2隊物品,那么第一對已經(jīng)取完保存在數(shù)組里面了,
那么從s[2][3*2+1]計算到s[2][n],
為什么這樣就可以呢?
仔細想下,第2組,前面只要有2個可以作為最大的筷子了,一定滿足題目意思的了,所以一直計算下去,
狀態(tài)轉(zhuǎn)移方程和前面一樣~
dp[i][j]=min(dp[i-1][j-2]+(a[j]-a[j-1])*(a[j]-a[j-1]),dp[i][j-1]);
ps:排序從大到小很精妙~
閱讀全文
hdu 1421 搬寢室
摘要: 由于數(shù)據(jù)還是比較大的，初始化時一定要足夠大，很容易錯！
dp[i][j] 從前i個物品中選取j對物品。
閱讀全文
hdu 2670 Girl Love Value
摘要: dp[i][j] 從前i個人中選j個的最優(yōu)值。
底層為從前i個選1個。
閱讀全文
hdu 2059 龜兔賽跑
摘要: 在同學(xué)的悉心教導(dǎo)之下總算做對了，雖然還不是很懂~
閱讀全文