夏令营7.19总结
动态规划
全称dynamic programming,DP
狭义上是子问题的递推。广义上等于递推，但是几乎不考虑。
三要素：
- 子问题（状态）
- 递推式（状态转移）
- 边界条件（边界状态）
$DP$的两种方式
- 后向$DP$填表法$pull\ DP$从前往后更新
- 前向$DP$刷表法$push\ DP$从后往前找哪些可以更新状态，并更新。
在一个序列上的$DP$：序列又两种子结构前缀（一个参数）和区间（两个参数）。
可以使用$DP$的数据结构：
- 序列
- 网络
- 数
- ……..
例一
例一就是简单递推。
目标：$f[N]$
边界条件：$f[0]=1,f[1]=2$。
递推式：$f[i]=f[i-1]+f[i-2],2\le i$
T1 构造序列
这题可以贪心，因为只能在最后添加。
目标：$f[N]$
边界条件：$f[0]=0$
递推式：$f[j]\le f[j+1]（0\le j\le N）$
一次性添加的项数越大越好。
T2 阿弥陀签的数量
由于各行都相对独立，所以从上往下考虑每一行。
定义$g[i][j]$表示：对于前$i$行，又多少种画法使得从$(0,1)$经过$i$步到达$(i,j)$。
边界条件：$g[0][1]=1$。
T3 Knapsack 2
边界条件：$f[0][0]=0,f[0][j]=W+1,j=1,…..,10^5$
递推式：对于$i=1,…,N$，有递推式：
$$
f[i][j] =
\begin{cases}
f[i - 1][j], & 0 \leq j < v_i, \
\min(f[i - 1][j], f[i - 1][j - v_i] + w_i), & v_i \leq j \leq 10^5.
\end{cases}
$$
T4 盒饭2
一看就是日本的题目
定义$f[i][j][k]$代表前$i$个盒饭吃了$j$个鱼丸$k$代表了最多的盒饭数。
想清思路，盒饭数较少但是鱼丸，肉丸数较多。所以盒饭数很重要。
例题$N+2$：分成三队
看到输出-1，你想到了什么？
空间计算：
$f[i][j][k]$中$i\le10^2,j\le500,k\le500$，总共$\le2.5\times10^7$，没问题。
目标：$f[N][M][M]$
边界条件：$f[0][0][0]=0,f[0][i][j]=N+1,i\ne0或j\ne0$
递推式：
第一队：$f[i-1][j-B_i][k]+(A_i\ne1),B_i\le j$
第二队：$f[i-1][j][k-B_i]+(A_i\ne2),B_i\le k$
第三队：$f[i-1][j][k]+(A_i\ne3)$
例题383_f：abc383f Diversity
按照颜色分组，一次只处理同一颜色的物品。
目标：$f[N][X]$
边界条件：$f[0][j]=0,0\le j\le X$
递推式：
对于每种颜色$i=1,…,N$：
- 将$f[i][j]$置为$f[i-1][j],0\le j\le X$
- 对于每个颜色是$i$的物品$(P,U)$，按照$j=X,X-1,…,P$的顺序，置$f[i][j]=max(f[i][j],f[i-1][j-P]+U+K,f[i][j-p]+U)$
T6 分组
目标：$f[N][0][X]$
边界条件：$f[0][0][k]=1(0\le k\le X)$
递推式：不好写，看图片吧
