题目列表-动态规划

1. 任务安排（斜率优化+费用提前计算）

   $$
   f[i]=min_{0\le j<i}{f[j]-(S+T[i])*C[i]+T[i]*C[i]+S*C[N]}
   $$

2. 特别行动队（斜率优化）

   $$
   f[i]=max_{0\le j<i}{f[j]+A*(S[i]-S[j])^2+B*(S[i]-S[j])+C}
   $$

3. 玩具装箱（斜率优化）

   $$
   f[i]=min_{0\le j<i}{f[j]+(A[i]-A[j]-L-1)^2}
   $$
   斜率优化的适用范围是只有一个自变量。

   形如这样的转移方程：
   $$
   f[i]=min_{0\le j<i}{f[j]+(i-j+S[i]-S[j]-L-1)^2}
   $$

   操作难度较大，可以将$S[i]+i$存在$A$数组中，即可全部化为一个自变量。

4. 锯木厂选址（斜率优化）

   $$
   f[i]=min_{1\le j<i}{C[i-1]-W[j]*(D[i]-D[j])}
   $$

5. 打印文章（斜率优化）

   $$
   f[i]=min_{0\le j<i}{f[j]+(S[i]-S[j])^2+M}
   $$
   调到心态爆炸……getK函数中如果除数为0则要返回1e100

6. 序列分割（斜率优化）

   $$
   f[i][j]=max_{0 \le k<j}{f[i-1][k]+S[k]*(S[j]-S[k])}
   $$
   不开long long见祖宗。题目中如果说“非负整数”一定记得判断除数是否为0。

   对于转移方程中的第一维，稍加观察就会发现可以使用滚动数组。（虽然也需要一些额外的数组记录状态）

7. 绿色通道（二分答案+单调队列）

   $$
   f[i]=min_{i-M-1 \le j <i}{f[j]+a[i]}
   $$

二分发怒程度$M$，$f$数组中存储选择当前题目最少多少体力。统计最终答案只需检验最后$M$个状态即可。

1
2

int ans=INF;
for(register int i=N-M;i<=N;++i) ans=min(ans,f[i]);

8. 股票交易（单调队列+很多条件）

   $$
   f[i][j]=-AP[i]*j(0 \le j \le AS[i])
   $$

   $$
   f[i][j]=max{f[i][j],f[i-1][j]}(0 \le j \le M)
   $$

   $$
   f[i][j]=max_{j-AS[i] \le k<j}{f[i-W-1][k]-(j-k)*AP[i]}(0 \le j \le M)
   $$

   $$
   f[i][j]=max_{j<k \le j+BS[i]}{f[i-W-1][k]+(k-j)*BP[i]}(0 \le j \le M)
   $$
   条件特别多，需要仔细分析题意并且列出状态转移方程。先进行较简单的转移，再利用单调队列进行复杂转移。注意第四种状态转移要使用逆序循环。

   如此恶心的状态转移让我不禁想起飞扬的小鸟

9. 潜入行动（背包类树形dp）

   $$
   f[u][i+j][0][0]=\sum f[u][i][0][0]*f[v][j][0][1]
   $$

   $$
   f[u][i+j][1][0]=\sum f[u][i][1][0]*(f[v][j][0][0]+f[v][j][0][1])
   $$

   $$
   f[u][i+j][0][1]=\sum (f[u][i][0][1]*(f[v][j][0][1]+f[v][j][1][1])+f[u][i][0][0]*f[v][j][1][1]
   $$

   $$
   f[u][i+j][1][1]=\sum (f[u][i][1][0]*(f[v][j][1][0]+f[v][j][1][1])+f[u][i][1][1]*(f[v][j][0][0]+f[v][j][0][1]+f[v][j][1][0]+f[v][j][1][1]))
   $$

   题解链接

   特别注意空间问题，中间运算转long long，保存时再转int

10. 子串（线性dp+滚动数组）

    $$
    f[i][0][0][0]=1
    $$

    $$
    f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]
    $$

    $$
    a[i]=b[j]:f[i][j][k][1]=f[i-1][j-1][k][1]+f[i-1][j-1][k-1][0]+f[i-1][j-1][k-1][1]
    $$

    $$
    a[i] \ne b[j]:f[i][j][k][1]=0
    $$

    滚动数组注意点：

    • 状态转移方程只依赖前一维或前两维状态
    • 状态数组要被滚动的一维只开1或2
    • 对于0/1滚动数组，可以结合位运算&和^进行判断奇偶性和减一操作

11. 换教室（期望dp）

    $$
    f[i][j][0]=min{f[i-1][j][0]+dis[C[i-1]][C[i]],f[i-1][j][1]+K[i-1]*dis[D[i-1]][C[i]]+(1-K[i-1])*dis[C[i-1]][C[i]]}
    $$

    $$
    f[i][j][1]=min{f[i-1][j-1][0]+K[i]*dis[C[i-1]][D[i]]+(1-K[i])*dis[C[i-1]][C[i]],f[i-1][j-1][1]+K[i-1]*K[i]*dis[D[i-1]][D[i]]+K[i-1]*(1-K[i])*dis[D[i-1]][C[i]]+(1-K[i-1])*K[i]*dis[C[i-1]][D[i]]+(1-K[i-1])*(1-K[i])*dis[C[i-1]][C[i]]}
    $$

    期望dp可以单独开一维表示状态，以便于列举出所有情况。本题的转移方程是一个很好的例子。如果tth37开心的话，Ta可能会写一篇数学期望专题具体讲解此类题目。

12. 过河（线性dp+玄学离散化）

    $$
    f[i]=min_{S \le j \le T}{f[i-j]+flag[i]}
    $$

    由于m非常小，因此采用2520缩点，即两点之间距离超过2520的，可以将距离改为$dis % 2520$，从而离散化。

13. 统计单词个数（线性dp+字符串）

    $$
    f[i][j]=max{f[i][j],f[r][j-1]+g[r+1][i]}
    $$

    字符串处理使用string类find函数。

    线性dp时再次强调，需要分清阶段、状态和决策变量；阶段在最外层循环，决策在最内层。在寻找关系时可以从推导或定义角度辨析，也可以根据转移方程进行识别。

14. 有线电视网（背包类树形dp）

    $$
    f[u][i]=max_{v\in son(u)}{f[u][i-j]+f[v][j]-w}
    $$
    题解链接

15. 棋盘制作（单调栈）

    似乎没有转移方程

    注意单调栈的处理方式（玄学方法或通用方法），在退栈时务必退干净。

1
2
3
4
5
6
7
8
9
10

//玄学方法：
for(register int i=1;i<=N+1;++i){
    while(cnt>0&&a[s[cnt]]>=a[i]){
        ans=max(ans,(i-s[cnt-1]-1)*a[s[cnt]]);
        cnt--;
    }
    s[++cnt]=i;
}
//通用方法：
先处理出每个位置左边第一个比它小的，再处理出右边第一个比它小的，最后枚举