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