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

转转来 發表於 2019-8-7 19:36:00

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

<h1 id="学习笔记动态规划各种-dp-优化">【学习笔记】动态规划—各种 DP 优化</h1>
<h2 id="大前言">【大前言】</h2>
个人认为贪心，\(dp\) 是最难的，每次遇到题完全不知道该怎么办，看了题解后又瞬间恍然大悟（TAT）。这篇文章也是花了我差不多一个月时间才全部完成。
<hr>
<h3 id="进入正题">【进入正题】</h3>
用动态规划解决问题具有空间耗费大、时间效率高的特点，但也会有时间效率不能满足要求的时候，如果算法有可以优化的余地，就可以考虑时间效率的优化。
<hr>
<h3 id="dp-时间复杂度的分析">【DP 时间复杂度的分析】</h3>
\(DP\) 高时间效率的关键在于它减少了“冗余”，即不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。而动态规划就是在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少“冗余”。 
但是，一个动态规划问题很难做到完全消除“冗余”。
下面给出动态规划时间复杂度的决定因素：
时间复杂度 \(=\) 状态总数 \(×\) 每个状态转移的状态数 \(×\) 每次状态转移的时间
<hr>
<h3 id="dp-优化思路">【DP 优化思路】</h3>
<h4 id="一减少状态总数">一：减少状态总数</h4>
\((1).\) 改进状态表示
\((2).\)选择适当的规划方向
<h4 id="二减少每个状态转移的状态数">二：减少每个状态转移的状态数</h4>
\((1).\) 四边形不等式和决策的单调性
\((2).\) 决策量的优化
\((3).\) 合理组织状态
\((4).\) 细化状态转移
<h4 id="三减少状态转移的时间">三：减少状态转移的时间</h4>
\((1).\) 减少决策时间
\((2).\) 减少计算递推式的时间
（上述内容摘自 《动态规划算法的优化技巧》毛子青 ，想要深入了解其思想的可以去看看这篇写得超级好的论文。）
<hr>
看到这里是不是已经感觉有点蒙了呢？ 
本蒟蒻总结了一个简化版本：
<hr>
<h3 id="dp-三要点">【DP 三要点】</h3>
在推导 \(dp\) 方程时，我们时常会感到毫无头绪，而实际上 \(dp\) 方程也是有迹可循的，总的来说，需要关注两个要点：状态，决策和转移。其中 “状态” 又最为关键，决策最为复杂。
<h4 id="状态">【状态】</h4>
关于 “状态” 的优化可以从很多角度出发，思维难度及其高，有时候状态选择的好坏会直接导致出现暴零和满分的分化。
<h4 id="决策">【决策】</h4>
与 “状态” 不同，“决策” 优化则有着大量模板化的东西，在各大书籍，文章上你都可以看到这样的话：只要是形如 \(XXX\) 的状态转移方程，都可以用 \(XXX\) 进行优化。
<h4 id="转移">【转移】</h4>
“转移” 则指由最优决策点得到答案的转移过程，其复杂度一般较低，通常可以忽略，但有时也需要特别注意并作优化。
本文将会重点针对 “决策” 优化部分作一些总结，记录自己的感悟和理解。
<hr>
<div class="math display">\[QAQ
\]</div><hr>
<h2 id="一矩阵优化-dp">一：【矩阵优化 DP】</h2>
\(updata\) 之后由于篇幅过大，已搬出。。。。。
【学习笔记】动态规划—矩阵递推加速
补充：其实质是优化 “转移”。
<hr>
<div class="math display">\[QAQ
\]</div><hr>
<h2 id="二数据结构优化-dp">二：【数据结构优化 DP】</h2>
<h3 id="前言">【前言】</h3>
在一些 \(dp\) 方程的状态转移过程中，我们通常需要在某个范围内进行择优，选出最佳决策点，这往往可以作为 \(dp\) 优化的突破口。
数据结构的使用较灵活，没有一个特定的模板，需要根据具体情况而定，选择合适的方案。由于状态转移总是伴随着区间查询最值，区间求和等操作，即动态区间操作，所以平衡树可以作为一个有用的工具，但考虑到代码复杂度，使用树状数组或者线段树将会是一个不错的选择。。
其实质是优化 “决策”。
<hr>
<h3 id="1维护合适的信息">1.【维护合适的信息】</h3>
以 \(The\) \(Battle\) \(of\) \(Chibi\) \(\) 为例，大概题意就是计算在给定的序列中严格单调递增子序列的数量，并对 \(1e9
+7\) 取模，给定序列长度小于等于 \(1000\) 。
方程应该是比较好推的，用 \(dp\) 表示由序列中在 \(j\) 之前的数构成并以 \(a\) 结尾的子序列中，长度为 \(i\) 的子序列的数量。则：\(dp=\sum dp\) ，其中 \(k < j\) \(且\) \(a < a\) 。
对于决策点 \(dp\) 这里出现了 \(3\) 个信息： 
\((1).\) 在原序列中的位置 \(k<j\) 。 
\((2).\) \(a<a\) 。 
\((3).\) \(dp\) 的和。
对于 \((1)\)，可以用枚举的顺序解决，剩下的两个信息即是数据结构需要维护的信息。
对于每一次 \(dp\) 的决策，可以将 \(a\) 作为数据结构维护的关键字， \(dp\) 作为权值，加入 \(-inf\) 后离散化，得到一个大小为 \(N+1\) 的数组并在上面建立树状数组，每次计算 \(dp\) 时查询前面已经加入的且关键字小于 \(a\) 的 \(dp\) 总和（即区间查询），然后把 \(dp\) 加入树状数组（单点查询）。
时间复杂度为 \(O(logn)\)。
当问题涉及到的操作更复杂时，树状数组无法维护所需要的信息，就只有用线段树了。这道题较简单，所以选择了代码复杂度更低的树状数组。
<hr>
<h3 id="2code">2.【Code】</h3>
<pre><code class="language-cpp">#include<algorithm>
#include<cstring>
#include<cstdlib>//UVA抽风，加上这个就好了
#include<cstdio>
#define Re register int
using namespace std;//UVA抽风，还要加这个
const int N=1005,P=1e9+7;
int n,m,T,k,ans,cnt,a,b,C,dp;
inline void add(Re x,Re v){while(x<=n+1)(C+=v)%=P,x+=x&-x;}
inline int ask(Re x){Re ans=0;while(x)(ans+=C)%=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),b=a,dp=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=ask((k=lower_bound(b+1,b+cnt+1,a)-b)-1),add(k,dp);
 }
 for(Re j=1;j<=n;++j)(ans+=dp)%=P;
 printf("Case #%d: %d\n",o,ans);
}
}
</code></pre>
<hr>
<h3 id="3题目链接">3.【题目链接】</h3>
<h4 id="简单题">【简单题】</h4>
<ul>
<li>\(The\) \(Battle\) \(of\) \(Chibi\) \(\) 
【标签】动态规划/树状数组</li>
</ul>
<h4 id="高档题">【高档题】</h4>
<ul>
<li>
方伯伯的玉米田 \(\) 
【标签】动态规划/二维树状数组
</li>
<li>
基站选址 \(\) 
【标签】动态规划/线段树
</li>
</ul>
<hr>
<div class="math display">\[QAQ
\]</div><hr>
<h2 id="三决策单调性">三：【决策单调性】</h2>
<h3 id="前言-1">【前言】</h3>
形如 \(dp=min(dp+w(j,i))\) \((L_i \leqslant j \leqslant R_i)\) 的 \(dp\) 方程被称作 \(1D/1D\) 动态规划，其中 \(L_i\) 和 \(R_i\) 单调递增，\(w(j,i)\) 决定着优化策略选择。
针对决策点具有的特性，可以大大降低寻找最优决策点的时间。
其实质是优化 “决策”。
<hr>
<h3 id="1定义">1.【定义】</h3>
<h4 id="决策单调性">【决策单调性】</h4>
设 \(j_0\) 表示 \(dp\) 转移的最优决策点，那么决策单调性可描述为 \(\forall i \leqslant j,j_0 \leqslant j_0\)。也就是说随着 \(i\) 的增大，所找到的最优决策点是递增态（非严格递增）。
<h4 id="四边形不等式">【四边形不等式】</h4>
\(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)\) 函数的二维矩阵中挖一块四边形，左上角 加 右下角 小于等于 左下角 加 右上角。
<hr>
<h3 id="2定理及其证明">2.【定理及其证明】</h3>
<h4 id="定理-1四边形不等式的另一种定义">定理 (1)：四边形不等式的另一种定义</h4>
\(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)\)
<h4 id="定理-2决策单调性">定理 (2)：决策单调性</h4>
\(1D/1D\) 动态规划具有决策单调性当且仅当函数 \(w\) 满足四边形不等式 时成立。
\(证明：\)
\(\because\) \(j_0\) \(在\) \(dp\) \(的决策点中最优\) 
\(\therefore\) \(\forall i \in ,\forall j \in -1],dp]+w(j_0,i) \leqslant dp+w(j,i)\)
\(易知\) \(\forall i' \in \)，\(均满足\) \(j<j_0<i<i'\)。 
\(又\) \(\because\) \(函数\) \(w\) \(满足四边形不等式\) 
\(\therefore\) \(w(j,i)+w(j_0,i') \leqslant w(j,i')+w(j_0,i)\)
\(移项得：\) \(w(j_0,i')-w(j_0,i) \leqslant w(j,i')-w(j,i)\)
\(与第一个式子相加，有：\) \(dp]+w(j_0,i') \leqslant dp+w(j,i')\)
最后的式子含义是：把 \(j_0\) 作为 \(dp\) 的决策点，一定比小于 \(j_0\) 的任意一个 \(j\) 都要更好。也就是说，\(dp\) 的最优决策点不可能小于 \(j_0\) ，即 \(j_0 \geqslant j_0\)，所以方程 \(dp\) 具有决策单调性。
<hr>
<h3 id="3证明决策单调性">3.【证明决策单调性】</h3>
这里以玩具装箱 \(toy\) \(\) 为例（因为这个比较好证 QAQ），先来证一波决策单调性。
设 \(S=\sum _{i=1}^n (C+1)\)，用 \(dp\) 表示装好前 \(i\) 个的最小花费，则 \(dp\) 方程为：\(dp=min(dp+(S-S-1-L)^2)\)。
很明显，这个方程是一个 \(1D/1D\) 动态规划方程，其中 \(w(i,j)=(S-S-1-L)^2\)。
（注意在四边形不等式中的 \(j\) 不是 \(i\) 决策点，可以理解为 \(i’\)。而 \(w(i,j)\) 的值可以理解为是由已完成的状态 \(dp\) 转移到 \(dp\) 所带有的附加价值）。
\(证明：设\) \(Q=S-S-1-L\)
\(\therefore w(i,j)=(S-S-1-L)^2=Q^2\)
\(\text{证明：设}\) \(Q=S-S-1-L\)
\(\therefore w(i,j)=(S-S-1-L)^2=Q^2\)
\(\begin{aligned}
\therefore w(i+1,j+1)=&(S-S-1-L)^2\\
 =&((S+C+1)-(S+C+1)-1-L)^2\\
 =&(Q+C-C)^2
\end{aligned}\)
\(\begin{aligned}
w(i,j+1)=&(S-S-1-L)^2\\
 =&(S-(S+C+1)-1-L)^2\\
 =&(Q-C-1)^2
\end{aligned}\)
\(\begin{aligned}
w(i+1,j)=&(S-S-1-L)^2\\
 =&((S+C+1)-S-1-L)^2\\
 =&(Q+C+1)^2
\end{aligned}\)
\(\therefore w(i,j)+w(i+1,j+1)=2X^2+2CX-2CX+C^2-2CC+C^2\)
\(\therefore w(i+1,j)+w(i,j+1)=2X^2+2CX-2CX+C^2+2C+2C+C^2+2\)
\(\therefore w(i,j)+w(i+1,j+1)-w(i+1,j)+w(i,j+1)=-2(C+1)(C+1)\)
\(\text{又} \because C,C \geqslant 1\)
\(\therefore -2(C+1)(C+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+2CX-2CX+C^2-2CC+C^2\)
\(\therefore w(i+1,j)+w(i,j+1)=2X^2+2CX-2CX+C^2+2C+2C+C^2+2\)
\(\therefore w(i,j)+w(i+1,j+1)-w(i+1,j)+w(i,j+1)=-2(C+1)(C+1)\)
\(又 \because C,C \geqslant 1\)
\(\therefore -2(C+1)(C+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\) 函数的递变规律。
<hr>
<h3 id="4实现方法">4.【实现方法】</h3>
（\(ps.\) 对于此处及以下语言不严谨处，大家可以认真思考并给予建议，待日后对其理解加深后再行修改。）
这里选择不同的例题将二者分开讲。
<h4 id="二分栈">【二分栈】</h4>
二分栈，顾名思义就是二分加栈。
用栈维护单调的决策点，二分找到最优决策点。
以 \(Lightning\) \(Conductor\) \(\) 为例，题目大意就是在给定长度为 \(n\) 的序列 \(a\) 中，对于每一个 \(i\)，找到最小的自然数 \(p_i\) 满足对于任意的 \(j \in \)，均有 \(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 ),max\{a_j+\sqrt{j-i}\}(j \in ) \}-a_i\)
可以发现里面两个 \(max\) 可以视为同一个问题（只要把序列翻转一下就可以了），所以只需要考虑求出对于每一个 \(i\) 的 \(max\{ a_j+\sqrt{i-j} \}\)，其中 \(j \in \)。
设 \(y_j=a_j+\sqrt{i-j}\)
那么我们会得到 \(n\) 个关于 \(i\) 函数，\(p_i=max\{ y_j \}\)。
将样例画出来，如图： 
<img src="https://images.cnblogs.com/cnblogs_com/Xing-Ling/1457207/o_bdf.PNG" alt="" loading="lazy">
可知当 \(i=4\) 时，直线 \(x=4\) 与 \(y1=a_1+\sqrt{x-1}\) 的交点即为 \(p_4\)。
在上图中，对于任意 \(j \in \) ，\(y1\) 总是在最上面，也就是说下面的其他函数可以踢掉不要，但由于 \(sqrt\) 函数的增速递减，会出现如图中 \(y2,y4\) 的情况，即存在一个交点使得在该点两边时两条直线的位置关系不同。此时如果没有上面的 \(y1\)，\(y2,y4\) 都有可能成为答案，所以不能乱踢。
看下面这种情况： 
<img src="https://images.cnblogs.com/cnblogs_com/Xing-Ling/1457207/o_nsdbs.PNG" alt="" loading="lazy">
设 \(k_1\) 为 \(y_1,y_2\) 的交点，\(k_2\) 为 \(y_2,y_3\) 的交点。 
此时 \(k_1 > k_2\)，可以发现 \(y_2\) 始终在其他直线的下面，可以放心的将其踢掉。
所以维护出来的决策集合大概就是酱紫的： 
<img src="https://images.cnblogs.com/cnblogs_com/Xing-Ling/1457207/o_hydtuydu.PNG" alt="" loading="lazy">
对于不同的 \(i\) 来说，都有一个互不不同的直线在最上方，所以该决策集合里的直线都是有用的。可以从图中看出，最优决策点单调递增（决策单调性的数学证明较麻烦，本人能力不足，不作探讨）。
维护决策集合用单调队列，查找直线交点用二分，随便搞搞就行了。
时间复杂度为 \(O(nlogn)\)。
<h4 id="分治">【分治】</h4>
为方便描述，用 \(dp\) 表示 \(dp,dp,dp...dp\)。
假设我们已知 \(dp\) 的最优决策点均位于 \(\)，再设 \(dp\) 的最优决策点为 \(j_0\)，其中 \(mid=(l+r)/2\)。根据决策单调性的定义可知： 
\(dp\) 的最优决策点位于 \(\)， 
\(dp\) 的最优决策点位于 \(\)。 
原问题变成了两个规模更小的同类型问题，所以可以用分治来对 \(dp\) 进行优化。
分治的话理解和代码都要简单一些，但在某些情况下可能要被卡，时间复杂度会严重退化，所以还是二分栈的实用性更高。
还是以 \(Lightning\) \(Conductor\) \(\) 为例，每次的分治中先暴力扫一遍找到 \(p\) 的最优决策点 \(j_0\)，然后做一下左边，再做一下右边，然后 \(...\) 然后 \(...\) 就没了。
时间复杂度为 \(O(nlogn)\)。
<hr>
<h3 id="5code">5.【Code】</h3>
<h4 id="二分栈-1">二分栈</h4>
<pre><code class="language-cpp">#include<algorithm>
#include<cstdio>
#include<cmath>
#define Re register int
using namespace std;
const int N=5e5+3;
int i,j,n,h,t,a,Q,Poi;
double p,sqr;
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+sqr;}
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<t&&Poi>=find_Poi(Q,i))--t;//如果出现了上述可踢的情况，出队
Poi=find_Poi(Q,i),Q[++t]=i;
while(h<t&&Poi<=i)++h;
//找到第一个位置j使得直线Q与直线Q的交点大于i，
//那么直线Q就是i前面在最上面的直线，即答案，自己画个图模拟一下就懂了
p=max(p,Y(i,Q));
}
}
int main(){
in(n);
for(Re i=1;i<=n;++i)in(a),sqr=sqrt(i);
sakura();
for(Re i=1;i<n-i+1;++i)swap(a,a),swap(p,p);
sakura();
for(Re i=n;i;--i)printf("%d\n",(int)ceil(p)-a);
}
</code></pre>
<h4 id="分治-1">分治</h4>
<pre><code class="language-cpp">#include<algorithm>
#include<cstdio>
#include<cmath>
#define Re register int
using namespace std;
const int N=5e5+3;
int i,j,n,h,t,a,Q,Poi;
double tmp,p,sqr;
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的最优决策点j0，而其决策点j必须满足j<=i，即此处的j<=mid
if((tmp=a+sqr)>mx)mx=tmp,j0=j;
p=max(p,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),sqr=sqrt(i);
sakura(1,n,1,n);
for(Re i=1;i<n-i+1;++i)swap(a,a),swap(p,p);
sakura(1,n,1,n);
for(Re i=n;i;--i)printf("%d\n",(int)ceil(p)-a);
}
</code></pre>
<hr>
<h3 id="6题目链接">6.【题目链接】</h3>
<h4 id="中档题">【中档题】</h4>
<ul>
<li>
\(Lightning\) \(Conductor\) \(\) 
【标签】动态规划/决策单调性
</li>
<li>
\(Noi\) 嘉年华 \(\) 
【标签】动态规划/决策单调性
</li>
<li>
大佬 \(\) 
【标签】动态规划/决策单调性
</li>
</ul>
<h4 id="高档题-1">【高档题】</h4>
<ul>
<li>诗人小 \(G\) \(\) 
【标签】动态规划/单调队列/贪心</li>
</ul>
<hr>
<div class="math display">\[QAQ
\]</div><hr>
<h2 id="四单调队列优化-dp">四：【单调队列优化 DP】</h2>
<hr>
<h3 id="前言-2">【前言】</h3>
形如 \(dp=max/min \{ dp+funtion(i)+function(j) \}\) 的 \(dp\) 方程均可尝试使用单调队列优化。
单调栈和单调队列给我们展现出了一种思想：在保证正确性的前提下，及时排除不可能的决策点，保持决策集合内部的有序性和查找决策的高效性。之前的二分栈，此处的单调队列优化，和后面的斜率优化都是以此为核心来运作的。
其实质是优化 “决策”。
<hr>
<h3 id="1单调队列的简单运用">1.【单调队列的简单运用】</h3>
<h4 id="t1">【T1】</h4>
琪露诺 \(\)（盗版滑动窗口QAQ）。
<h5 id="题目大意">【题目大意】</h5>
在给定序列中找出一条路径使其经过的点之和最大，且每次可走的距离在给定区间 \(\) 以内。
<h5 id="分析">【分析】</h5>
方程非常简单：\(dp=max\{ dp+a \} (i-r \leqslant j \leqslant i-l)\) 。
在某一次决策中，由于决策点 \(j\) 只可能在 \(\) 这一段区间内，可以只将这些点放入决策集合。 
而 \(l,r\) 是定值，当 \(i\) 不断增大时，之前小于 \(i-l\) 的 \(j\) 现在还是小于 \(i-l\)，所以可以永远地踢掉。 
若 \(j < j'\) 且 \(dp \leqslant dp\)，那么 \(dp\) 也可以永远地踢掉。为什么呢？ \(j\) 在 \(j'\) 的前面，一定会先成为不合法决策点，而 \(j\) 的价值又比 \(j'\) 小，因此留下来只是浪费扫描的时间。
最终维护出了一个价值递减的单调队列。
<h5 id="code">【Code】</h5>
<pre><code class="language-cpp">#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using std::max;
const int N=2e5+3;
int n,l,r,h=1,t,a,Q;
long long ans=-2e9,dp;
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);
dp=a;
for(Re i=l;i<=n;i++){//注意枚举起点是l不是1
while(h<=t&&dp]<=dp)--t;//维护单调递减
Q[++t]=i-l;//入队
while(h<=t&&Q<i-r)++h;//保证决策点合法
dp=dp]+a;//取出最优决策点
if(i>n-r)ans=max(ans,dp);
}
printf("%lld",ans);
}
</code></pre>
<h4 id="t2">【T2】</h4>
\(fence\) \(\)
<h5 id="题目大意-1">【题目大意】</h5>
\(M\) 个工人要对 \(N\) 块木板进行粉刷。工人 \(i\) 要么不刷，要么就刷不超过 \(L_i\) 块并且包含 \(S_i\) 的连续一段木板，每粉刷一块木板有 \(P_i\) 的报酬。要求使总报酬最大。
<h5 id="分析-1">【分析】</h5>
\(S_i\) 的散乱分布非常讨厌，所以先把工人按 \(S_i\) 排个序。
主要信息有“工人序号”，“木板序号”，“报酬”这三个，而其中“报酬”为所求答案，可以用 \(dp\) 表示前 \(i\) 个工人刷完前 \(j\) 块木板所得总报酬。
考虑状态转移： 
第 \(i\) 个工人可以跳过不刷木板，也可以跳过第 \(j\) 块木板不刷，因此先在 \(dp\) 和 \(dp\) 当中取个最大值。 
工人 \(i\) 想要粉刷的区间 \(\) 必须包括 \(S_i\)，并且区间长度要小于等于 \(L_i\)。 
所以得出 \(dp\) 转移方程：\(dp=max \{ dp,dp,dp+P_i*(j-k) \}\)，其中 \(S_i \leqslant j\) 且 \(k \in \)。
\(k\) 为决策点，\(P_i*j\) 为定值可以单独提出来，所以实际上就是上面琪露诺 \(\)一样的类型，只是加了一维而已。
最终维护出了一个 \(dp-P_i*k\) 递减的单调队列。
<h5 id="code-1">【Code】</h5>
<pre><code class="language-cpp">#include<algorithm>
#include<cstring>
#include<cstdio>
#define Re register int
using namespace std;
const int N=16005;
struct QAQ{int L,P,S;}a;
int n,m,i,j,k,Q,W,dp;
inline bool cmp(QAQ a,QAQ b){return a.S<b.S;}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(dp,0,sizeof(dp));
memset(a,0,sizeof(a));
for(i=1;i<=m;++i)scanf("%d%d%d",&a.L,&a.P,&a.S);
std::sort(a+1,a+m+1,cmp);
for(i=1;i<=m;++i){
 Re l=1,r=0,tmp,Si=a.S,Li=a.L,Pi=a.P;
 for(k=max(0,Si-Li);k<Si;++k){
 //k+1为工人i开始刷的位置，max(1,Si-Li+1)<=k+1<=Si
 tmp=dp-Pi*k;
 while(l<=r&&Q<=tmp)--r;
 Q[++r]=tmp,W=k;
 }
 for(j=1;j<=n;++j){
 dp=max(dp,dp);
 if(Si+Li>j&&j>=Si){//Si+Li-1>=j>=Si
 while(l<=r&&W+Li<j)++l;//W+1+Li-1<j
 if(l<=r)dp=max(dp,Q+Pi*j);
 }
 }
}
printf("%d\n",dp);
}
}
</code></pre>
<hr>
<h3 id="2单调队列优化多重背包">2.【单调队列优化多重背包】</h3>
先来回顾一下多重背包问题。
用 \(v,w,c\) 分别表示物品重量，价值，数量，\(n\) 为物品数量，\(V\) 为背包容量。\(dp\) 方程为：\(dp=max\{ dp]+k*w \}\) \((j \in ,V],\) \(k \in ,j/v)])\)
还可以用二进制拆分来进行优化，但就是有这样一道题，连 \(log\) 都要卡：多重背包 \(\)。所以还需要考虑更高效的算法。
但说来说去似乎都和单调队列扯不上关系。
为何？
观察 \(dp\) 和 \(dp\) 决策集合： 
\(dp: \{ j \% v...j-2*v,j-v \}\) 
\(dp: \{ (j-1) \% v...(j-1)-2*v,(j-1)-v \}\)
\(dp\) 的每一个决策点都与 \(dp\) 不同，很难根据 \(dp\) 的决策集合转移成 \(dp\) 的决策集合。
再看 \(dp\) 和 \(dp]\)：
\(dp: \{ j-c*v...j-2v,j-v \}\)
\(dp]: \{ j-(c+1)*v...j-3v,j-2v \}\)
可以发现上面只是比下面的区别仅仅在于 \(j-(c+1)*v\) 和 \(j-v\) ，恰好满足单调队列的一个特性：但有新的决策出现时，决策点集合中会去掉一部分不合法的，再加上一部分新来的。
所以我们可以按照 \(j%v\) 的余数来分一下：
\(dp(j\%v=0):\{0,v,2v...j-2v,j-v\}\) 
\(dp(j\%v=1):\{1,v+1,2v+1...j-2v,j-v \}\) 
\(...\) 
\(dp(j\%v=v-1):\{v-1,2v-1...j-2v,j-v\}\)
设 \(j=p*v+r\)，那么原方程可改为： \(dp+r]=max\{ dp]+(p-k)*w \}\) \((r \in -1],\) \(p \in \rfloor],\) \(k \in \rfloor ,c),p])\) 
只要在最外层将 \(i,r,p\) 都枚举出来，这就是一个标准的单调队列可优化方程，用类似 \(fence\) \(\) 的方法维护即可。
时间复杂度为 \(O(N*V)\) 。
<h4 id="code-2">【Code】</h4>
<pre><code class="language-cpp">#include<cstdio>
#define Re register int
const int N=7003,M=7003;
int n,h,t,V,mp,tmp,v,w,c,Q,K,dp;
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 a<b?a:b;}
int main(){
in(n),in(V);
for(Re i=1;i<=n;++i)in(v),in(w),in(c);
for(Re i=1;i<=n;++i)
for(Re r=0;r<v;++r){
 h=1,t=0,mp=(V-r)/v;
 for(Re p=0;p<=mp;++p){
 tmp=dp+r]-w*p;
 while(h<=t&&Q<=tmp)--t;
 Q[++t]=tmp,K=p;
 while(h<=t&&p-K>min(c,V/v))++h;
 dp+r]=max(dp+r],Q+p*w);
 }
 }
printf("%d",dp);
}
</code></pre>
<hr>
<h3 id="3题目链接-1">3.【题目链接】</h3>
<h4 id="简单题-1">【简单题】</h4>
<ul>
<li>琪露诺 \(\) 
【标签】动态规划/单调队列</li>
</ul>
<h4 id="中档题-1">【中档题】</h4>
<ul>
<li>
\(fence\) \(\) 
【标签】动态规划/单调队列
</li>
<li>
多重背包 \(\) 
【标签】动态规划/单调队列/多重背包
</li>
<li>
我要长高 \(\) 
【标签】动态规划/单调队列
</li>
</ul>
<hr>
<div class="math display">\[QAQ
\]</div><hr>
<h2 id="五斜率优化-dp">五：【斜率优化 DP】</h2>
由于篇幅过大，已搬出。。。。。
【学习笔记】动态规划—斜率优化DP（超详细）
补充：其实质是优化 “决策”。
<hr>
<div class="math display">\[QAQ
\]</div><hr>
<h2 id="参考文献">【参考文献】</h2>
（本文部分内容摘自以下文章）
<ul>
<li>
\(dp\) 的各种优化
</li>
<li>
决策单调性优化
</li>
<li>
四边形不等式优化
</li>
<li>
四边形不等式学习笔记
</li>
<li>
四边形不等式优化讲解（详解）
</li>
<li>
单调队列优化的多重背包
</li>
<li>
动态规划的单调队列优化（含多重背包）
</li>
<li>
\(dp\) 基础 — \(DraZxINDdt\)
</li>
<li>
《算法竞赛进阶指南》李煜东
</li>
<li>
《动态规划算法的优化技巧》毛子青
</li>
</ul>

</div>
<div id="MySignature" role="contentinfo">
<div>
<img alt="知识共享许可协议" style="border-width:0" src="https://images.cnblogs.com/cnblogs_com/Xing-Ling/1635185/o_20062410573688x31.png" />

本作品采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。
</div>

 

<div>作者：辰星凌 (Xing_Ling)</div>

-----若要转载请私信作者获得许可并在文首标出转载来源----- 
来源：https://www.cnblogs.com/Xing-Ling/p/11317315.html

頁: [1]

琼殿技术论坛's Archiver

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