【总结】【模板】2021年寒假集训前期总结

本文主要是介绍【总结】【模板】2021年寒假集训前期总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0x00 前言

学了 DP 的优化和搜索的优化，说实话真的没什么可以总结的，但是还是强行安了几个模板，有的版块确实总结不出什么模板了，就暂且咕咕咕掉吧。。。

0x01 单调队列优化 DP

首先还是要写出 dp 式

一般是一个两重循环

第一重循环枚举阶段，第二重循环枚举前面的并更新后面

大致就是这样的：

$dp_i=\mathrm{min}_{(j-k+1)\to j}\{f(i)+g(j)\}$

其中 $f (i)$ 和 $g (j)$ ，分别表示的是与 $i$ 和 $j$ 有关的多项式/单项式

至于 $k$ ，由题目而定

由于 $i$ 在这个阶段是固定的，所以把 $f (i)$ 给分离出来

$dp_i=\mathrm{min}_{(j-k+1)\to j}\{g(j)\}+f(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式： $dp_i=min(dp_j+(sum_i-sum_j)^2+m)$ ， $sum_i$ 表示的是前缀和
然后不妨设 $k$ 转移过劳比 $j$ 转移过来优，且 $k$ 再 $j$ 后面
即
$dp_j+(sum_i-sum_j)^2+m \geq dp_k+(sum_i-sum_k)^2+m$
然后对上面这个不等式化简，注意 $k$ 再 $j$ 后，所以 $sum_k \geq sum_j$
$\frac{(sum_k^2+dp_k)-(sum_j^2+dp_j)}{sum_k-sum_j} \geq 2sum_i$

于是上面这个是分子，下面这个是分母，右边那个是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;
}