【学习笔记】动态规划—各种 DP 优化

【大前言】

个人认为贪心，\(dp\) 是最难的，每次遇到题完全不知道该怎么办，看了题解后又瞬间恍然大悟（TAT）。这篇文章也是花了我差不多一个月时间才全部完成。

【进入正题】

用动态规划解决问题具有空间耗费大、时间效率高的特点，但也会有时间效率不能满足要求的时候，如果算法有可以优化的余地，就可以考虑时间效率的优化。

【DP 时间复杂度的分析】

\(DP\) 高时间效率的关键在于它减少了“冗余”，即不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。而动态规划就是在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少“冗余”。
但是，一个动态规划问题很难做到完全消除“冗余”。

下面给出动态规划时间复杂度的决定因素：

时间复杂度 \(=\) 状态总数 \(×\) 每个状态转移的状态数 \(×\) 每次状态转移的时间

【DP 优化思路】

一：减少状态总数

\((1).\) 改进状态表示

\((2).\)选择适当的规划方向

二：减少每个状态转移的状态数

\((1).\) 四边形不等式和决策的单调性

\((2).\) 决策量的优化

\((3).\) 合理组织状态

\((4).\) 细化状态转移

三：减少状态转移的时间

\((1).\) 减少决策时间

\((2).\) 减少计算递推式的时间

（上述内容摘自 《动态规划算法的优化技巧》毛子青 ，想要深入了解其思想的可以去看看这篇写得超级好的论文。）

看到这里是不是已经感觉有点蒙了呢？
本蒟蒻总结了一个简化版本：

【DP 三要点】

在推导 \(dp\) 方程时，我们时常会感到毫无头绪，而实际上 \(dp\) 方程也是有迹可循的，总的来说，需要关注两个要点：状态，决策和转移。其中 “状态” 又最为关键，决策最为复杂。

【状态】

关于 “状态” 的优化可以从很多角度出发，思维难度及其高，有时候状态选择的好坏会直接导致出现暴零和满分的分化。

【决策】

与 “状态” 不同，“决策” 优化则有着大量模板化的东西，在各大书籍，文章上你都可以看到这样的话：只要是形如 \(XXX\) 的状态转移方程，都可以用 \(XXX\) 进行优化。

【转移】

“转移” 则指由最优决策点得到答案的转移过程，其复杂度一般较低，通常可以忽略，但有时也需要特别注意并作优化。

本文将会重点针对 “决策” 优化部分作一些总结，记录自己的感悟和理解。

一：【矩阵优化 DP】

\(updata\) 之后由于篇幅过大，已搬出。。。。。

补充：其实质是优化 “转移”。

二：【数据结构优化 DP】

【前言】

在一些 \(dp\) 方程的状态转移过程中，我们通常需要在某个范围内进行择优，选出最佳决策点，这往往可以作为 \(dp\) 优化的突破口。

数据结构的使用较灵活，没有一个特定的模板，需要根据具体情况而定，选择合适的方案。由于状态转移总是伴随着区间查询最值，区间求和等操作，即动态区间操作，所以平衡树可以作为一个有用的工具，但考虑到代码复杂度，使用树状数组或者线段树将会是一个不错的选择。。

其实质是优化 “决策”。

1.【维护合适的信息】

以 \(The\) \(Battle\) \(of\) \(Chibi\) \([UVA12983]\) 为例，大概题意就是计算在给定的序列中严格单调递增子序列的数量，并对 \(1e9 +7\) 取模，给定序列长度小于等于 \(1000\) 。

方程应该是比较好推的，用 \(dp[i][j]\) 表示由序列中在 \(j\) 之前的数构成并以 \(a[j]\) 结尾的子序列中，长度为 \(i\) 的子序列的数量。则：\(dp[i][j]=\sum dp[i-1][k]\) ，其中 \(k < j\) \(且\) \(a[k] < a[j]\) 。

对于决策点 \(dp[i-1][k]\) 这里出现了 \(3\) 个信息：
\((1).\) 在原序列中的位置 \(k 。
\((2).\) \(a[k] 。
\((3).\) \(dp[i-1][k]\) 的和。

对于 \((1)\)，可以用枚举的顺序解决，剩下的两个信息即是数据结构需要维护的信息。

对于每一次 \(dp[i]\) 的决策，可以将 \(a[j]\) 作为数据结构维护的关键字， \(dp[i-1][j]\) 作为权值，加入 \(-inf\) 后离散化，得到一个大小为 \(N+1\) 的数组并在上面建立树状数组，每次计算 \(dp[i][j]\) 时查询前面已经加入的且关键字小于 \(a[j]\) 的 \(dp[i-1][k]\) 总和（即区间查询），然后把 \(dp[i-1][j]\) 加入树状数组（单点查询）。

时间复杂度为 \(O(logn)\)。

当问题涉及到的操作更复杂时，树状数组无法维护所需要的信息，就只有用线段树了。这道题较简单，所以选择了代码复杂度更低的树状数组。

2.【Code】

#include
#include
#include//UVA抽风，加上这个就好了
#include
#define Re register int
using namespace std;//UVA抽风，还要加这个
const int N=1005,P=1e9+7;
int n,m,T,k,ans,cnt,a[N],b[N],C[N],dp[N][N];
inline void add(Re x,Re v){while(x<=n+1)(C[x]+=v)%=P,x+=x&-x;}
inline int ask(Re x){Re ans=0;while(x)(ans+=C[x])%=P,x-=x&-x;return ans%P;}
int main(){
    scanf("%d",&T);
    for(Re o=1;o<=T;++o){
        scanf("%d%d",&n,&m),ans=0,cnt=n;
        memset(dp,0,sizeof(dp));
        for(Re i=1;i<=n;++i)scanf("%d",&a[i]),b[i]=a[i],dp[1][i]=1;
        sort(b+1,b+n+1);//离散
        cnt=unique(b+1,b+n+1)-b-1;//去重
        for(Re i=2;i<=m;++i){
            memset(C,0,sizeof(C));//每次都要清空，重新开始维护
            for(Re j=1;j<=n;++j)
                dp[i][j]=ask((k=lower_bound(b+1,b+cnt+1,a[j])-b)-1),add(k,dp[i-1][j]);
        }	
        for(Re j=1;j<=n;++j)(ans+=dp[m][j])%=P;
        printf("Case #%d: %d\n",o,ans);
    }
}

3.【题目链接】

【简单题】

• \(The\) \(Battle\) \(of\) \(Chibi\) \([UVA12983]\)
  【 标签】动态规划/树状数组

【高档题】

• 方伯伯的玉米田 \([P3287]\)
  【 标签】动态规划/二维树状数组

• 基站选址 \([P2605]\)
  【 标签】动态规划/线段树

三：【决策单调性】

【前言】

形如 \(dp[i]=min(dp[j]+w(j,i))\) \((L_i \leqslant j \leqslant R_i)\) 的 \(dp\) 方程被称作 \(1D/1D\) 动态规划，其中 \(L_i\) 和 \(R_i\) 单调递增，\(w(j,i)\) 决定着优化策略选择。

针对决策点具有的特性，可以大大降低寻找最优决策点的时间。

其实质是优化 “决策”。

1.【定义】

【决策单调性】

设 \(j_0[i]\) 表示 \(dp[i]\) 转移的最优决策点，那么决策单调性可描述为 \(\forall i \leqslant j,j_0[i] \leqslant j_0[j]\)。也就是说随着 \(i\) 的增大，所找到的最优决策点是递增态（非严格递增）。

【四边形不等式】

\(w(x,y)\) 为定义在整数集合上的一个二元函数，若 \(\forall a \leqslant b \leqslant c \leqslant d,w(a,c)+w(b,d) \leqslant w(a,d)+w(b,c)\)，那么函数 \(w\) 满足四边形不等式。

为什么叫做四边形不等式呢？在 \(w(x,y)\) 函数的二维矩阵中挖一块四边形，左上角 加 右下角 小于等于 左下角 加 右上角。

2.【定理及其证明】

定理 (1)：四边形不等式的另一种定义

\(w(x,y)\) 为定义在整数集合上的一个二元函数，若 \(\forall a < b,w(a,b)+w(a+1,b+1) \leqslant w(a+1,b)+w(a,b+1)\)，那么函数 \(w\) 满足四边形不等式。

\(证明：\)

\(\because \forall a < c,w(a,c)+w(a+1,c+1) \leqslant w(a+1,c)+w(a,c+1)\)

\(\therefore \forall a+1 < c,w(a+1,c)+w(a+2,c+1) \leqslant w(a+2,c)+w(a+1,c+1)\)

\(上下两式相加，有：\) \(w(a,c)+w(a+2,c+1) \leqslant w(a,c+1)+w(a+2,c)\)

\(以此类推\) \(\forall a \leqslant b\leqslant c,w(a,c)+w(b,c+1) \leqslant w(a,c+1)+w(b,c)\)

\(同理\) \(\forall a \leqslant b \leqslant c \leqslant d,w(a,c)+w(b,d) \leqslant w(a,d)+w(b,c)\)

定理 (2)：决策单调性

\(1D/1D\) 动态规划具有决策单调性当且仅当函数 \(w\) 满足四边形不等式 时成立。

\(证明：\)

\(\because\) \(j_0[i]\) \(在\) \(dp[i]\) \(的决策点中最优\)
\(\therefore\) \(\forall i \in [1,N],\forall j \in [0,j_0[i]-1],dp[j_0[i]]+w(j_0[i],i) \leqslant dp[j]+w(j,i)\)

\(易知\) \(\forall i' \in [i+1,N]\)，\(均满足\) \(j。
\(又\) \(\because\) \(函数\) \(w\) \(满足四边形不等式\)
\(\therefore\) \(w(j,i)+w(j_0[i],i') \leqslant w(j,i')+w(j_0[i],i)\)

\(移项得：\) \(w(j_0[i],i')-w(j_0[i],i) \leqslant w(j,i')-w(j,i)\)

\(与第一个式子相加，有：\) \(dp[j_0[i]]+w(j_0[i],i') \leqslant dp[j]+w(j,i')\)

最后的式子含义是：把 \(j_0[i]\) 作为 \(dp[i']\) 的决策点，一定比小于 \(j_0[i]\) 的任意一个 \(j\) 都要更好。也就是说，\(dp[i’]\) 的最优决策点不可能小于 \(j_0[i]\) ，即 \(j_0[i'] \geqslant j_0[i]\)，所以方程 \(dp\) 具有决策单调性。

3.【证明决策单调性】

这里以 玩具装箱 \(toy\) \([P3195]\) 为例（因为这个比较好证 QAQ），先来证一波决策单调性。

设 \(S[n]=\sum _{i=1}^n (C[i]+1)\)，用 \(dp[i]\) 表示装好前 \(i\) 个的最小花费，则 \(dp\) 方程为：\(dp[i]=min(dp[j]+(S[i]-S[j]-1-L)^2)\)。

很明显，这个方程是一个 \(1D/1D\) 动态规划方程，其中 \(w(i,j)=(S[i]-S[j]-1-L)^2\)。

（注意在四边形不等式中的 \(j\) 不是 \(i\) 决策点，可以理解为 \(i’\)。而 \(w(i,j)\) 的值可以理解为是由已完成的状态 \(dp[i]\) 转移到 \(dp[j]\) 所带有的附加价值）。

\(证明：设\) \(Q=S[i]-S[j]-1-L\)

\(\therefore w(i,j)=(S[i]-S[j]-1-L)^2=Q^2\)

\(\text{证明：设}\) \(Q=S[i]-S[j]-1-L\)

\(\therefore w(i,j)=(S[i]-S[j]-1-L)^2=Q^2\)

\(\begin{aligned} \therefore w(i+1,j+1)=&(S[i+1]-S[j+1]-1-L)^2\\ =&((S[i]+C[i+1]+1)-(S[j]+C[j+1]+1)-1-L)^2\\ =&(Q+C[i+1]-C[j+1])^2 \end{aligned}\)

\(\begin{aligned} w(i,j+1)=&(S[i]-S[j+1]-1-L)^2\\ =&(S[i]-(S[j]+C[j+1]+1)-1-L)^2\\ =&(Q-C[j+1]-1)^2 \end{aligned}\)

\(\begin{aligned} w(i+1,j)=&(S[i+1]-S[j]-1-L)^2\\ =&((S[i]+C[i+1]+1)-S[j]-1-L)^2\\ =&(Q+C[i+1]+1)^2 \end{aligned}\)

\(\therefore w(i,j)+w(i+1,j+1)=2X^2+2C[i+1]X-2C[j+1]X+C[i+1]^2-2C[i+1]C[j+1]+C[j+1]^2\)

\(\therefore w(i+1,j)+w(i,j+1)=2X^2+2C[i+1]X-2C[j+1]X+C[i+1]^2+2C[i+1]+2C[j+1]+C[j+1]^2+2\)

\(\therefore w(i,j)+w(i+1,j+1)-w(i+1,j)+w(i,j+1)=-2(C[i+1]+1)(C[j+1]+1)\)

\(\text{又} \because C[i],C[j] \geqslant 1\)

\(\therefore -2(C[i+1]+1)(C[j+1]+1) \leqslant -8\)

\(\therefore w(i,j)+w(i+1,j+1) \leqslant w(i+1,j)+w(i,j+1)\)

\(\therefore w(i,j)+w(i+1,j+1)=2X^2+2C[i+1]X-2C[j+1]X+C[i+1]^2-2C[i+1]C[j+1]+C[j+1]^2\)

\(\therefore w(i+1,j)+w(i,j+1)=2X^2+2C[i+1]X-2C[j+1]X+C[i+1]^2+2C[i+1]+2C[j+1]+C[j+1]^2+2\)

\(\therefore w(i,j)+w(i+1,j+1)-w(i+1,j)+w(i,j+1)=-2(C[i+1]+1)(C[j+1]+1)\)

\(又 \because C[i],C[j] \geqslant 1\)

\(\therefore -2(C[i+1]+1)(C[j+1]+1) \leqslant -8\)

\(\therefore w(i,j)+w(i+1,j+1) \leqslant w(i+1,j)+w(i,j+1)\)

由定理 \((1)\) 可知，函数 \(w\) 满足四边形不等式。
又由定理 \((2)\)可知， 方程 \(dp\) 具有决策单调性。

在实战中，通常使用打表的形式来验证 \(w\) 函数的递变规律。

4.【实现方法】

（\(ps.\) 对于此处及以下语言不严谨处，大家可以认真思考并给予建议，待日后对其理解加深后再行修改。）

这里选择不同的例题将二者分开讲。

【二分栈】

二分栈，顾名思义就是二分加栈。

用栈维护单调的决策点，二分找到最优决策点。

以 \(Lightning\) \(Conductor\) \([P3515]\) 为例，题目大意就是在给定长度为 \(n\) 的序列 \(a\) 中，对于每一个 \(i\)，找到最小的自然数 \(p_i\) 满足对于任意的 \(j \in [1,n]\)，均有 \(a_j \leqslant a_i+p_i-\sqrt{\left|i-j\right|}\) 。

把这个式子变下形：\(p_i \geqslant a_j-a_i+\sqrt{\left|i-j\right|}\) 。
即 \(p_i=max \{ a_j+\sqrt{\left|i-j\right|} \} -a_i\)
即 \(p_i = max \{ max\{a_j+\sqrt{i-j}\}(j \in [1,i]),max\{a_j+\sqrt{j-i}\}(j \in [i+1,n]) \}-a_i\)

可以发现里面两个 \(max\) 可以视为同一个问题（只要把序列翻转一下就可以了），所以只需要考虑求出对于每一个 \(i\) 的 \(max\{ a_j+\sqrt{i-j} \}\)，其中 \(j \in [1,i]\)。

设 \(y_j=a_j+\sqrt{i-j}\)

那么我们会得到 \(n\) 个关于 \(i\) 函数，\(p_i=max\{ y_j \}\)。

将样例画出来，如图：

可知当 \(i=4\) 时，直线 \(x=4\) 与 \(y1=a_1+\sqrt{x-1}\) 的交点即为 \(p_4\)。

在上图中，对于任意 \(j \in [1,n]\) ，\(y1\) 总是在最上面，也就是说下面的其他函数可以踢掉不要，但由于 \(sqrt\) 函数的增速递减，会出现如图中 \(y2,y4\) 的情况，即存在一个交点使得在该点两边时两条直线的位置关系不同。此时如果没有上面的 \(y1\)，\(y2,y4\) 都有可能成为答案，所以不能乱踢。

看下面这种情况：

设 \(k_1\) 为 \(y_1,y_2\) 的交点，\(k_2\) 为 \(y_2,y_3\) 的交点。
此时 \(k_1 > k_2\)，可以发现 \(y_2\) 始终在其他直线的下面，可以放心的将其踢掉。

所以维护出来的决策集合大概就是酱紫的：

对于不同的 \(i\) 来说，都有一个互不不同的直线在最上方，所以该决策集合里的直线都是有用的。可以从图中看出，最优决策点单调递增（决策单调性的数学证明较麻烦，本人能力不足，不作探讨）。

维护决策集合用单调队列，查找直线交点用二分，随便搞搞就行了。

时间复杂度为 \(O(nlogn)\)。

【分治】

为方便描述，用 \(dp[a,b]\) 表示 \(dp[a],dp[a+1],dp[a+2]...dp[b]\)。

假设我们已知 \(dp[l,r]\) 的最优决策点均位于 \([L,R]\)，再设 \(dp[mid]\) 的最优决策点为 \(j_0\)，其中 \(mid=(l+r)/2\)。根据决策单调性的定义可知：
\(dp[l,mid-1]\) 的最优决策点位于 \([L,k]\)，
\(dp[mid+1,r]\) 的最优决策点位于 \([k,R]\)。
原问题变成了两个规模更小的同类型问题，所以可以用分治来对 \(dp\) 进行优化。

分治的话理解和代码都要简单一些，但在某些情况下可能要被卡，时间复杂度会严重退化，所以还是二分栈的实用性更高。

还是以 \(Lightning\) \(Conductor\) \([P3515]\) 为例，每次的分治中先暴力扫一遍找到 \(p[mid=(l+r)/2]\) 的最优决策点 \(j_0\)，然后做一下左边，再做一下右边，然后 \(...\) 然后 \(...\) 就没了。

时间复杂度为 \(O(nlogn)\)。

5.【Code】

二分栈

#include
#include
#include
#define Re register int
using namespace std;
const int N=5e5+3;
int i,j,n,h,t,a[N],Q[N],Poi[N];
double p[N],sqr[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline double Y(Re i,Re j){return a[j]+sqr[i-j];}
inline int find_Poi(int j1,int j2){//找到两个直线的交点i 
    Re l=j2,r=n,mid,ans=n+1;//为了处理两个直线没有交点的情况，用一个变量记录答案
    while(l<=r){
        mid=l+r>>1;
        if(Y(mid,j1)<=Y(mid,j2))ans=mid,r=mid-1;
//当前这个位置i使得直线j1的纵坐标小于直线j2的纵坐标，说明这个点i在交点的右方，所以右边界要缩小
        else l=mid+1;
    }
    return ans;
}
inline void sakura(){
    h=1,t=0;
    for(i=1;i<=n;++i){//由于i本身也是一个决策点，所以要先入队再取答案择优
    	while(h=find_Poi(Q[t],i))--t;//如果出现了上述可踢的情况，出队
    	Poi[t]=find_Poi(Q[t],i),Q[++t]=i;
    	while(h

#include
#include
#include
#define Re register int
using namespace std;
const int N=5e5+3;
int i,j,n,h,t,a[N],Q[N],Poi[N];
double tmp,p[N],sqr[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void sakura(Re l,Re r,Re L,Re R){
    if(l>r)return;
    Re mid=l+r>>1,j0;double mx=0;
    for(Re j=L;j<=mid&&j<=R;++j)
    //暴力找p[i]的最优决策点j0，而其决策点j必须满足j<=i，即此处的j<=mid
    	if((tmp=a[j]+sqr[mid-j])>mx)mx=tmp,j0=j;
    p[mid]=max(p[mid],mx);
    sakura(l,mid-1,L,j0),sakura(mid+1,r,j0,R);
}
int main(){
    in(n);
    for(Re i=1;i<=n;++i)in(a[i]),sqr[i]=sqrt(i);
    sakura(1,n,1,n);
    for(Re i=1;i

#include
#include
#include
#define Re register int
using std::max;
const int N=2e5+3;
int n,l,r,h=1,t,a[N],Q[N];
long long ans=-2e9,dp[N]; 
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
    in(n),in(l),in(r);
    memset(dp,-127,sizeof(dp));
    Q[++t]=0;
    for(Re i=0;i<=n;++i)in(a[i]);
    dp[0]=a[0];
    for(Re i=l;i<=n;i++){//注意枚举起点是l不是1
    	while(h<=t&&dp[Q[t]]<=dp[i-l])--t;//维护单调递减
    	Q[++t]=i-l;//入队
    	while(h<=t&&Q[h]n-r)ans=max(ans,dp[i]);
    }
    printf("%lld",ans);
}

#include
#include
#include
#define Re register int
using namespace std;
const int N=16005;
struct QAQ{int L,P,S;}a[105];
int n,m,i,j,k,Q[N],W[N],dp[105][N];
inline bool cmp(QAQ a,QAQ b){return a.Sj&&j>=Si){//Si+Li-1>=j>=Si
                    while(l<=r&&W[l]+Li

#include
#define Re register int
const int N=7003,M=7003;
int n,h,t,V,mp,tmp,v[N],w[N],c[N],Q[N],K[N],dp[M];
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline int max(Re a,Re b){return a>b?a:b;}
inline int min(Re a,Re b){return amin(c[i],V/v[i]))++h;
            	dp[p*v[i]+r]=max(dp[p*v[i]+r],Q[h]+p*w[i]);
            }
        }
    printf("%d",dp[V]);
}