本文主要是介绍【总结】【模板】2021年寒假集训前期总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
- 0x00 前言
- 0x01 单调队列优化 DP
- 0x02 斜率优化 DP
0x00 前言
学了 DP 的优化和搜索的优化，说实话真的没什么可以总结的，但是还是强行安了几个模板，有的版块确实总结不出什么模板了，就暂且咕咕咕掉吧。。。
0x01 单调队列优化 DP
首先还是要写出 dp 式
一般是一个两重循环
第一重循环枚举阶段，第二重循环枚举前面的并更新后面
大致就是这样的：
d p i = m i n ( j − k + 1 ) → j { f ( i ) + g ( j ) } dp_i=\mathrm{min}_{(j-k+1)\to j}\{f(i)+g(j)\} dpi=min(j−k+1)→j{f(i)+g(j)}
其中 f ( i ) f(i) f(i)和 g ( j ) g(j) g(j)，分别表示的是与 i i i 和 j j j 有关的多项式/单项式
至于 k k k，由题目而定
由于 i i i 在这个阶段是固定的，所以把 f ( i ) f(i) f(i) 给分离出来
d p i = m i n ( j − k + 1 ) → j { g ( j ) } + f ( i ) dp_i=\mathrm{min}_{(j-k+1)\to j}\{g(j)\}+f(i) dpi=min(j−k+1)→j{g(j)}+f(i)
然后对于 g ( i ) g(i) g(i)，即是求一个区间最小
直接套用单调队列就行了
int head=1,tail=1;
for(int i=1;i<=n;i++){if(i-k>q[head] && head<=tail){head++;}while(g(i)>g(q[tail]) && head<=tail){//这里的g(i)按题而定tail--;}用q[head]当做原本的j去更新dp[i];q[++tail]=i;
}
0x02 斜率优化 DP
推柿子是有点复杂，但最后套用模板是挺方便
由于题目千遍万化，没有办法直接表示，所以就以一道版题为例：
打印文章：
-
首先，写出dp式： d p i = m i n ( d p j + ( s u m i − s u m j ) 2 + m ) dp_i=min(dp_j+(sum_i-sum_j)^2+m) dpi=min(dpj+(sumi−sumj)2+m)， s u m i sum_i sumi 表示的是前缀和
-
然后不妨设 k k k转移过劳 比 j j j 转移过来优，且 k k k 再 j j j 后面
-
即
d p j + ( s u m i − s u m j ) 2 + m ≥ d p k + ( s u m i − s u m k ) 2 + m dp_j+(sum_i-sum_j)^2+m \geq dp_k+(sum_i-sum_k)^2+m dpj+(sumi−sumj)2+m≥dpk+(sumi−sumk)2+m -
然后对上面这个不等式化简，注意 k k k 再 j j j 后，所以 s u m k ≥ s u m j sum_k \geq sum_j sumk≥sumj
-
( s u m k 2 + d p k ) − ( s u m j 2 + d p j ) s u m k − s u m j ≥ 2 s u m i \frac{(sum_k^2+dp_k)-(sum_j^2+dp_j)}{sum_k-sum_j} \geq 2sum_i sumk−sumj(sumk2+dpk)−(sumj2+dpj)≥2sumi
于是上面这个是分子，下面这个是分母，右边那个是R(i)，盲猜是维护一个下凸壳（因为如果不是的话是无法套这个模板的）
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int MAXN=500005;
int n,m,q[MAXN],s[MAXN],dp[MAXN];
int getson(int k,int j){//do sth.
}
int getmon(int k,int j){//do sth.
}
int main(){int n,m;//init int head=1,tail=1;for(int i=1;i<=n;i++){while(head<tail && getson(q[head],q[head+1])<=R(i)*getmon(q[head],q[head+1])){head++;}dp[i]=dp[q[head]]+(s[i]-s[q[head]])*(s[i]-s[q[head]])+m;//这里使用q[head]当作暴力中的j去更新dp[i]while(head<tail && getson(q[tail],i)*getmon(q[tail-1],q[tail])<=getson(q[tail-1],q[tail])*getmon(q[tail],i)){tail--;}q[++tail]=i;}printf("%d\n",dp[n]);
return 0;
}
这篇关于【总结】【模板】2021年寒假集训前期总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
