【动态规划】“新手动态规划合集”题解

标签：题解 max 序列 长度 cases 动态 规划

动态规划三要素

阶段，状态，决策

动态规划经典模型

LIS（最长上升子序列）

给定长度为 \(N\) 的序列 \(A[i]\)，求出其最长上升子序列的长度。（以不严格上升为例）

• 阶段：已经处理的序列长度 \(i\)

• 状态：\(f[i]\) 表示以 \(A[i]\) 结尾的 LIS 长度

• 转移

\[f[i]=\max\limits_{j\in\left[1,i-1\right]\wedge A[j]\leq A[i]}f[j]+1 \]

这个转移是 \(\Theta(N^2)\) 的。事实上可以通过二分来优化到 \(\Theta(N\log N)\)，但是不甚通用。

LCS（最长公共子序列）

给定长度为 \(N\) 的序列 \(A[i]\) 和长度为 \(M\) 的序列 \(B[i]\)，求出其 LCS 长度。

• 阶段：\(A\) 已经处理的长度 \(i\)，\(B\) 已经处理的长度 \(j\)

• 状态：\(f[i,j]\) 表示 \(A[1..i]\) 与 \(B[1..j]\) 的 LCS 长度

• 转移

\[f[i,j]= \max\begin{cases} \max(f[i-1,j],f[i,j-1]), \\ f[i-1,j-1]+1, \text{if } A[i]=B[j] \end{cases}\]

时间复杂度 \(\Theta(NM)\)。

新手动态规划合集题单题解

P1359 租用游艇

给定从 \(i\) 到 \(j\) 的代价 \(w[i,j]\)（\(i\lt j\)），求出从 \(1\) 地到 \(N\) 地的最小代价。

设 \(f[i]\) 表示从 \(1\) 到 \(i\) 的最小代价。转移方程：

\[f[i]=\max\limits_{j\in[1,i-1]}\left(f[j]+w[j,i]\right) \]

初值：\(f[1]=0\)，其余均为正无穷。目标：\(f[n]\)。

P1060 [NOIP2006 普及组] 开心的金明

有 \(n\) 元，\(m\) 个物品。第 \(i\) 个物品价值为 \(v[i]\)，权值为 \(w[i]\)。选定一些物品，在 \(\sum w[i]\leq n\) 的前提下，\(\sum v[i]\times w[i]\) 最大。

这本质上是一个 0-1 背包问题。每个物品质量为 \(v[i]\)，价值为 \(v[i]\times w[i]\)。

于是设 \(f[i,j]\) 为考虑到第 \(i\) 个物品时，花费 \(j\) 元所得最大值。于是

\[f[i, j]=max(f[i,j],f[i-1,j-v[i]]+v[i]\times w[i]) \]

然后可以利用滚动数组优化，注意别滚反了。

P1802 5 倍经验日

有 \(x\) 瓶药，\(n\) 个人，对第 \(i\) 个人使用 \(m\) 瓶时，获得经验为

\[\begin{cases} win[i], m \geq use[i] \\ lose[i], m \lt use[i] \end{cases} \]

求出获得经验最大值。

这也是一个背包模型。设 \(f[i,j]\) 为考虑到第 \(i\) 个人，使用 \(j\) 瓶药时的经验最大值。于是

标签：题解,max,序列,长度,cases,动态,规划
From： https://www.cnblogs.com/Starrykiller/p/dp-part1.html