DP及优化

· · 个人记录

本博客只作概述，不做详解

同时挂出链接的题目笔者并未全部完成

由于笔者较懒，对于每种算法，仅给出少量题目作为例子

大佬请自觉跳过本博客第一部分（当然，大佬是不会来看我的博客的）

所以请大佬移步至其他大佬的博客

怎么说呢，这篇文章既不像知识普及性的博客，也不像题目众多的题单，所以，大概也没人看吧

DP-初探DP及其分类

定义

【OI Wiki】动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

基础DP

不作赘述

P1216 [IOI1994]数字三角形

P1091 [NOIP2004 提高组] 合唱队形

P1006 [NOIP2008 提高组] 传纸条

随便丢几道水题（红题难度）

(然后才发现为什么我P1006忘了写（恼

背包DP

推荐去看洛谷日报/背包九讲

基本模型包括但不限于01背包，完全背包，多重背包等

其中01背包第二个循环考虑倒序，多重背包有二进制拆分及单调队列优化

忘记哪里来的题单(虽然我就写了三分之一到二分之一差不多)

线性DP

单序列问题

【典】P1020 [NOIP1999 普及组] 导弹拦截

P4933 大师

多序列问题

【典】P1439 【模板】最长公共子序列

P2679 [NOIP2015 提高组] 子串

高维问题

P1004 [NOIP2000 提高组] 方格取数

区间&环形DP

区间DP

【典】P1435 [IOI2000] 回文字串

P1775 石子合并（弱化版）

环形DP

【典】P1880 [NOI1995] 石子合并

P1063 [NOIP2006 提高组] 能量项链

树&图上DP

树上DP

【典】P1352 没有上司的舞会

P2014 [CTSC1997] 选课

图上DP

P1613 跑路

P6772 [NOI2020] 美食家

状压DP

基础

P1896 [SCOI2005] 互不侵犯

按秩转移

*CF11D A Simple Task

与其他算法的混合使用

*P1357 花园

DP-优化从入门到入土

前缀和优化

当DP过程中需要反复从一个求和式转移的话，可以先把它预处理一下。运算一般都要满足可减性。

比较naive，多看看就好了

P2511 [HAOI2008]木棍分割

P4099 [HEOI2013]SAO

单调队列优化

P3800 Power收集

P2254 [NOI2005] 瑰丽华尔兹

单调栈优化

暂缺

线段树/树状数组优化

（线段树人傻常数大

CF833B The Bakery

斜率优化(Useless Algorithm)

好像已经超出NOIP的范围，稍作了解即可(除非你是神，不然考场上能写50分的暴力就别写这种做法的100分）

简而言之，就是把方程转化成f[i]=a(i)*b(j)+c(j)+(一个与i有关的常数)的形式，从而降维打击

P3195 [HNOI2008]玩具装箱

P3628 [APIO2010] 特别行动队

维护临界值/斜率单调
加入决策直线/决策点
弹出已经不优的决策
求出最优解

分治套斜率优化

更加没用（

P4027 [NOI2007] 货币兑换

四边形不等式优化(Useless Algorithm)

也是用不到的算法，甚至不用了解

当符合m(i,j)=min(m(i,k)+m(k+1,j)+w(i,j))，可以用四边形不等式降维

P4767 [IOI2000]邮局

f(i,j)=min(f(i-1,k)+w(k,j)$可用分治套决策单调性解决，问题同上线段树优化中的$The Bakery

分治优化DP模板

void DP(int l,int r,int kl,int kr){
    int mid=(l+r)>>1,k=kl;
    //求状态f[mid]的最优决策点
    for(int i=kl;i<=min(kr,mid-1);++i)if(slope(i,mid)<slope(k,mid))k=i;
    f[mid]=slope(k,mid);
    //根据决策单调性得出左右两部分的决策区间，递归处理
    if(l<mid)DP(l,mid-1,kl,k);
    if(r>mid)DP(mid+1,r,k,kr);
}

DP凸优化/WQS二分/带权二分(Useless Algorithm)

放心，绝对用不到（不排除您是神的情况）

WQS的论文

*P4383 [八省联考 2018] 林克卡特树

\mathcal{If you have nothing to hide, then you have nothing to fear.}