zju 1520 Duty Free Shop
摘要: 經(jīng)典背包，記錄路徑，放得下就行。
閱讀全文
zju 1503 One Person "The Price is Right"
摘要: 1503 估價(jià)游戲，一個(gè)決策為背景的 DP，當(dāng)前剩下 i 次機(jī)會(huì)和 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ù)][物品個(gè)數(shù)](I為I副筷子，J為總共筷子)
現(xiàn)在轉(zhuǎn)入正題,這個(gè)題目要求每一組有3個(gè)筷子,前2個(gè)的差的平方最小,
首先和前面題目一樣先排序?qū)Π?顯然從大到小排(因?yàn)檫@樣完全可以轉(zhuǎn)化成搬寢室 那個(gè)一樣的思想)
比如取第2隊(duì)物品,那么第一對(duì)已經(jīng)取完保存在數(shù)組里面了,
那么從s[2][3*2+1]計(jì)算到s[2][n],
為什么這樣就可以呢?
仔細(xì)想下,第2組,前面只要有2個(gè)可以作為最大的筷子了,一定滿足題目意思的了,所以一直計(jì)算下去,
狀態(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ù)還是比較大的，初始化時(shí)一定要足夠大，很容易錯(cuò)！
dp[i][j] 從前i個(gè)物品中選取j對(duì)物品。
閱讀全文
hdu 2670 Girl Love Value
摘要: dp[i][j] 從前i個(gè)人中選j個(gè)的最優(yōu)值。
底層為從前i個(gè)選1個(gè)。
閱讀全文
hdu 2059 龜兔賽跑
摘要: 在同學(xué)的悉心教導(dǎo)之下總算做對(duì)了，雖然還不是很懂~
閱讀全文