動(dòng)態(tài)規(guī)劃
摘要: [狀態(tài)] f[i]表示從0到i點(diǎn)最少踩到的石子數(shù), stone[i]表示i點(diǎn)有無(wú)石子;
[方程] f[i] = max{f[i-j] + stone[i]} (S<=j<=T)
[初始化] f[0] = 0, 其他賦值為無(wú)限大.
閱讀全文
摘要: 樹(shù)形DP，需要記錄方案，并注意空樹(shù)的情況.
[狀態(tài)]f[i][j]從結(jié)點(diǎn)i到j(luò)的最大加分值
[方程]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)
實(shí)現(xiàn)方程的時(shí)候循環(huán)順序非常關(guān)鍵:結(jié)點(diǎn)數(shù)由小到大循環(huán).否則會(huì)出現(xiàn)需要的值未計(jì)算的情況.
記錄方案可以用一個(gè)數(shù)組d[i][j]記錄k，然后遞歸尋找方案并記錄.
閱讀全文
摘要: 題目中附件不超過(guò)2個(gè)，因而主附件存在4種不同的存取情況，可以轉(zhuǎn)化為分組背包問(wèn)題.
[狀態(tài)]f[k][v]表示添加前k組物品，剩余空間為v時(shí)的最大值
[方程]f[k][v] = max{f[k-1][v], f[k-1][v-c[i]]+w[i]}
閱讀全文
摘要: 和2000的方格取數(shù)如出一轍.數(shù)據(jù)加強(qiáng)了一點(diǎn)，如果是裸的四維dp可能會(huì)超時(shí)(80).所以需要優(yōu)化.
閱讀全文
摘要: 簡(jiǎn)單dp，難點(diǎn)在于狀態(tài)的表示.
題目可以看做兩人同時(shí)取數(shù)，這樣就避免了后效性，可以用dp做了.
【狀態(tài)】f[i][j][k][l]表示兩人分別到(i,j)、(k,l)所取過(guò)的數(shù)的和.G[i][j]表示方格里的數(shù).
【方程】f[i][j][k][l] = max{f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1]}+G[i][j]+(i==k&&j==l ? 0 : G[k][l])
閱讀全文