Konata28

三层：阶段，状态，决策。

Hu Kang

以下均以 01 背包举例。

状态表示

将每一个状态看作一个集合集的属性。

\(f[i,j]\) 表示前 \(i\) 个物品中总体积为 \(j\) 的物品集合集的元素大小和的最大值（属性）。

\(e.g.\)

其中 \(\{1,2\}\) 的价值和最大，为 \(6+8=14\)，故 \(f[3,9]=14\)

常见的属性有：大小、最值、和、乘积、异或和……

状态转移

对集合集中集合的划分。

将 \(f[i,j]\) 的集合集划分成包含 \(i\) 物品的集合和不包含 \(i\) 物品的集合。

两种情况分别对应 \(f[i-1,j]\) 和 \(f[i-1,j-w_i]+v_i\)。

所以状态转移方程为 \(f[i,j]=\max(f[i-1,j],f[i-1,j-w_i]+v_i)\)。

\(e.g.\)

蓝色为不含 \(i\) 的，红色为含 \(i\) 的。

再思考，可以用滚动数组优化空间复杂度。

Unknown

拿到一道题，先写出状态转移方程，再优化时间复杂度

状态优化：

对于状态可累加
\(e.g.dp[i+j]=dp[i]+dp[j]+i+j\)
的，用倍增优化

决策优化：

\(e.g.dp[i][j]=\max(dp[i-1][j-233]+(j-233)^2,dp[i-1][j-232]+(j-232)^2,...,dp[i-1][j]+j^2)\)
单调队列优化

\(e.g.dp[i]=\max(dp[1]+i,dp[2]+2i,...,dp[i-1]+(i-1)i)\)
斜率优化

交叉小于包含
\(e.g.dp[i][j]=\max(dp[i][i]+dp[i+1][j],dp[i][i+1]+dp[i+2][j],...,dp[i][j-1]+dp[j-1][j],dp[i][j]+dp[j][j])\)
用四边形不等式优化