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