专栏文章

动态规划指南

HHisy
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mint9npf
此快照首次捕获于
2025/12/02 07:59
3 个月前
此快照最后确认于
2025/12/02 07:59
3 个月前
查看原文

定义

Dp⁡\operatorname{Dp} 全称为 Dynamic⁡Planing⁡\operatorname{Dynamic} \operatorname{Planing}，动态规划。通过设计 dpdp 的递推式子，通过已经求出的东西算出还未求出的东西。
很明显，动态规划是按照拓扑序进行规划的，比如规划了 ii 之后，其他的规划就可以使用 dpidp_i。根据这个要求，我们可以知道 dpdp 仅适用于没有后效性的题目，就是可能需要两个 dpdp 互相更新，算完一个之后还需要继续更新。

递推（线性）Dp⁡\operatorname{Dp}

通常来讲，线性 dpdp 是最简单的，通常是一维到两维，这也是回忆作为萌新刚刚接触 Dp⁡\operatorname{Dp} 时的唯一的柔光。

LIS⁡单调子序列\operatorname{LIS} 单调子序列

令 dpidp_i 为末尾为第 ii 个数的最长上升子序列，很明显有 dpi=max⁡1≤j<i[aj≤ai](dpj+1)dp_i=\max_{1\le j<i}[a_j\le a_i](dp_j+1)，这样是 O⁡(n2)\operatorname{O}(n^2) 复杂度的算法。然而，还有更快的算法。
CPP
#define MAXN 1010
using namespace std;
int n,a[MAXN],dp[MAXN];
int main(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<i;++j){
			if(a[j]<=a[i]){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
	}
}
已知需要维护在 ii 前面比 ii 小的数，那么则不需要考虑在 i+0.5i+0.5 位置往前面看的时候看得到的数。发现这样子很想之前讲的单调栈。所以，我们考虑单调栈维护，使单调栈从小到大。
但是，出队的时间复杂度太高了，最坏情况需要将整个栈重新更新。因为栈内单调，所以可以使用二分查找到第一个将该元素插入保持单调的数。在深入浅出中，lower_bound⁡\operatorname{lower\_bound} 和 upper_bound⁡\operatorname{upper\_bound} 的定义就是这样子的。考虑使用二分，复杂度 O⁡(nlog⁡n)\operatorname{O}(n\log n)。具体在数据结构板块实现。

LIC⁡\operatorname{LIC} 最长公共子序列

令 dpi,jdp_{i,j} 表示第一个序列选到第 ii 个，第二个序列选到第 jj 个的最大长度。很明显有 dpdp 式：
\max(dp_{i-1,j},dp_{i,j-1}) & \operatorname{otherwise} \end{cases}$$ ```cpp #define MAXN 1010 using namespace std; int n,a[MAXN],b[MAXN],dp[MAXN][MAXN]; int main(){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(a[i]^b[j]){ dp[i][j]=max(dp[i-1][j],dp[i][j-1]); }else{ dp[i][j]=dp[i-1][j-1]+1; } } } } ``` 有部分题目，$a$ 的范围很小，但是 $n$ 很大，所以对于这些题目可以使用位并行技术，即为压位（将每 $w$ 个元素压成一个 ```long long``` 类型，时间复杂度 $\operatorname{\frac{n\times m}{w^2}}$。 ### 斐波那契数列 很明显，令 $dp$ 式有： $$dp_i=\begin{cases} 0 & i=0\\ 1 & i=1\\ dp_{i-2}+dp_{i-1} & \operatorname{otherwise} \end{cases}$$ 时间复杂度 $\operatorname{O}(n)$。在 $\operatorname{Dp}$ 优化里面会有 $\log n$ 的矩阵快速幂做法。 ## 背包 $\operatorname{Dp}$ ### 定义 解决形如： > 有 $n$ 个物品，你有一个背包最大能够装下大小总和为 $m$ 的物品。每一个物品大小为 $v_i$，价值为 $w_i$，你需要求出背包里面物品最大价值总和。 ### $01$ 背包 令 $dp_{i,j}$ 为当前选到第 $i$ 个物品，剩余背包容量为 $j$，对于相同 $i$，不同 $j$ 有 $dp_{i,j}=dp_{i-1,j-v_i}+w_i$。 考虑到第一维没有用，可以使用滚动数组滚掉一维。 ```cpp #define MAXN 1010 using namespace std; int n,m,v[MAXN],w[MAXN],dp[MAXN]; int main(){ for(int i=1;i<=n;++i){ for(int j=m;j>=v[i];--j){ for(int k=0;k<=j-v[i];++k){ dp[j]=max(dp[j],dp[k]+w[i]); } } } } ``` ### 变体：完全背包 在这个基础上，每一个元素可以选择无限次。 考虑对于每一个容量，令 $dp_v$ 为剩余容量为 $v$ 的最大价值。遍历 $n$，对于每一个物品计算最大值（一定要从小往大更新），因为多选的选项需要建立在之前选过一次。 ```cpp #define MAXN 1010 using namespace std; int n,m,v[MAXN],w[MAXN],dp[MAXN]; int main(){ for(int i=1;i<=n;++i){ for(int j=v[i];j<=m;++j){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } } ``` ### 变体：多重背包 每一个物品可以选择 $c_i$ 个。 #### 方法 $1$：二进制分组 考虑到每一个物品最多选择 $c_i$ 个，在 $[1,c_i]$ 之间的数在二进制下必定能够被 $c_i$ 表示出来，所以考虑将 $c_i$ 拆分成二进制，就是按照取 $1$ 个、取 $2$ 个、取 $4$ 个……取 $2^n$ 个。 #### 方法 $2$：单调队列优化（在 $\operatorname{Dp}$ 优化里面介绍。 #### [模板题](https://www.luogu.com.cn/problem/P2871) ```cpp #include<cstdio> #define max(cmp1,cmp2) ((cmp1)>(cmp2)?(cmp1):(cmp2)) int plan[1000001]={0}; int main(int argc,char **argv){ int maxn,maxm,weight,worth; scanf("%d %d",&maxn,&maxm); for(int it=1;it<=maxn;it++){ scanf("%d %d",&weight,&worth); for(int fex=maxm;fex>=weight;fex--){ plan[fex]=max(plan[fex],plan[fex-weight]+worth); }; }; printf("%d",plan[maxm]); return 0; }; ``` #### [模板题](https://www.luogu.com.cn/problem/P1616) 完全背包模板题。 ```cpp #include<bits/stdc++.h> #define MAXN 10001 #define MAXM 10000001 using namespace std; typedef long long ll; ll v[MAXN],w[MAXN],dp[MAXM]; int main(){ int m,n; scanf("%d %d",&m,&n); for(int i=1;i<=n;++i){ scanf("%lld %lld",&w[i],&v[i]); } for(int i=1;i<=n;++i){ for(int j=w[i];j<=m;++j){ dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } printf("%lld",dp[m]); return 0; } ``` ## 区间 $\operatorname{Dp}$ 区间 $\operatorname{Dp}$ 通常是指 $dp_{l,r}$ 表示为 $[l,r]$ 之间的答案，可以说算是仅次于背包的模板题目了。 转移状态通常是先枚举长度，然后枚举左端点，然后枚举中转点，使 $dp_{l,r}=\max_{l\le k<r}\{dp_{l,k}+dp_{k+1,r}\}$。 ```cpp #define MAXN 1010 using namespace std; int n,dp[MAXN][MAXN]; int main(){ for(int len=1;len<=n;++len){ for(int l=1,r=len;r<=n;++l,++r){ for(int mid=l;mid<r;++mid){ dp[l][r]=max(dp[l][k]+dp[k+1][r]); } } } } ``` #### [例题](https://www.luogu.com.cn/problem/P4302) 令 $dp_{l,r}$ 为 $[l,r]$ 内最小次数，如果 $[l,r]$ 能够组成折叠那么就可以更新答案，其他情况直接合并即可。 这里有一个注意点，区间 $\operatorname{Dp}$ 一定不要对时间有所顾虑，通常复杂度已经是 $\operatorname{O}(n^3)$ 了，在外面加一个暴力判断是不会多加指数的，一定要敢想敢打。 ```cpp #include<bits/stdc++.h> #define MAXN 110 using namespace std; int n,dp[MAXN][MAXN]; char str[MAXN]; inline int digit(int num){ int cnt=0; while(num){ num/=10; ++cnt; } return cnt; } inline bool check(int l,int r,int siz){ for(int i=l;i<=l+siz-1;++i){ for(int j=i;j<=r;j+=siz){ if(str[i]^str[j]){ return false; } } } return true; } int main(){ scanf("%s",str+1); n=strlen(str+1); memset(dp,0x3f,sizeof(dp)); for(int i=1;i<=n;++i){ dp[i][i]=1; } for(int len=2;len<=n;++len){ for(int l=1,r=len;r<=n;++l,++r){ for(int mid=l;mid<r;++mid){ dp[l][r]=min(dp[l][r],dp[l][mid]+dp[mid+1][r]); int siz=mid-l+1; if(len%siz||!check(l,r,siz)){ continue; } dp[l][r]=min(dp[l][r],dp[l][mid]+digit(len/siz)+2); } } } printf("%d",dp[1][n]); return 0; } ``` #### [例题](https://www.luogu.com.cn/problem/UVA1437) 虽然是 $\operatorname{UVA}$ 的题目，但是毋庸置疑是比较有创新的一道题目。 考虑维护 $dp_{l,r}$ 为将 $S_{[l,r]}$ 转为一样的字符的最小次数，然后继续维护一个 $f_i$ 表示将前 $i$ 个字符转换之后再次转换成 $B$ 的次数。 ```cpp #include<bits/stdc++.h> using namespace std; int dp[MAXN][MAXN],f[MAXN]; string S,B; inline void solve(){ memset(dp,0x3f,sizeof(dp)); memset(f,0x3f,sizeof(f)); for(size_t i=0;i<S.size();++i){ dp[i][i]=1; } for(size_t s=1;s<S.size();++s){ for(size_t l=0,r=s;r<S.size();++l,++r){ if(B[l]==B[r]){ dp[l][r]=min(dp[l+1][r],dp[l][r-1]); }else{ for(size_t i=l;i<r;++i){ dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]); } } } } f[0]=1; if(S.front()==B.front()){ f[0]=0; } for(size_t i=1;i<S.size();++i){ f[i]=dp[0][i]; if(S[i]==B[i]){ f[i]=f[i-1]; } for(size_t j=0;j<i;++j){ f[i]=min(f[i],f[j]+dp[j+1][i]); } } cout<<f[S.size()-1]<<endl; } int main(){ ios::sync_with_stdio(0); while(cin>>S>>B){ solve(); } return 0; } ``` ## 树形 $\operatorname{Dp}$ 树形 $\operatorname{Dp}$ 为在树上进行的动态规划，通过递归从叶子节点更新答案直至根节点，或者从根节点遍历至叶子节点。 通常来讲，树形 $\operatorname{Dp}$ 有几个常考的思路： - $dp_{root}$：以 $root$ 为根的子树的答案。 - $dp_{root,0/1}$：在 $root$ 节点被染成黑或白的情况下的答案。 - $dp_{root,cnt}$：在 $root$ 节点之下，剩余 $cnt$ 步数的答案。 - $dp_{root,cnt,0/1}$：令以 $root$ 为根的子树下，有 $cnt$ 个被染成了黑色，$root$ 节点染成黑或白。 ### 变体：换根 $\operatorname{Dp}$ 令 $dp_i$ 为以 $i$ 为根节点的时候的答案，是十分毒瘤的 $\operatorname{Dp}$，仅次于插头 $\operatorname{Dp}$ 和 状压 $\operatorname{Dp}$。 通常来讲，第一次需要预处理以 $1$ 为节点的深度、距离、答案等因素，第二次则需要开始动态修改根节点。 #### [例题](https://www.luogu.com.cn/problem/P4815) 具体参考[我的题解](https://www.luogu.com.cn/article/epixko36)，只是想要吐槽一下没有狼踩狼，匪徒这也太容易暴露了吧。 #### [模板题](https://www.luogu.com.cn/problem/P3478) 令 $dp_u$ 为当前的 $u$ 为根节点，当换成 其他的子节点作为根节点的时候，则该子节点路径上所有深度减一，即减去 $siz_v$，其他部分加一，即加上 $siz_v$，就是加上 $n-siz_v$。于是便有了 $\operatorname{Dp}$ 式子，$dp_v=dp_u+n-2\times siz_v$。 ```cpp #include<bits/stdc++.h> #define MAXN 1000010 using namespace std; using ll=long long; struct node{ int to,next; node(int to=0,int next=0){ this->to=to; this->next=next; } }edge[MAXN<<1]; int n,cnt,head[MAXN],siz[MAXN],dep[MAXN]; ll dp[MAXN]; inline void addedge(int from,int to){ edge[++cnt]=node(to,head[from]); head[from]=cnt; } inline void init(int from,int fa){ dep[from]=dep[fa]+1; siz[from]=1; for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(to^fa){ init(to,from); siz[from]+=siz[to]; } } } inline void dfs(int from,int fa){ for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(to^fa){ dp[to]=dp[from]+n-2*siz[to]; dfs(to,from); } } } int main(){ scanf("%d",&n); for(int i=1;i<n;++i){ int from,to; scanf("%d %d",&from,&to); addedge(from,to); addedge(to,from); } init(1,0); for(int i=1;i<=n;++i){ dp[1]+=dep[i]; } dfs(1,0); int root=1; for(int i=2;i<=n;++i){ if(dp[root]<dp[i]){ root=i; } } printf("%d",root); return 0; } ``` ## 状压 $\operatorname{Dp}$ 状态压缩即是把很多维的 $\operatorname{Dp}$ 压缩成一个 ```int``` 类型的数。通常为压缩二进制，```zip``` 表示为在二进制下每一位的状态（例如走没走过，选没选过）。 常用二进制算法如下： - ```zip|=1<<(i-1)```：将 ```zip``` 第 $i$ 位修改成 $1$。 - ```zip^=1<<(i-1)```：将 ```zip``` 第 $i$ 位取反。 - ```zip&(1<<(i-1))```：查询第 $i$ 位。 - ```zip>>(i-1)&1```：同样为查询第 $i$ 位。 - ```zip=(1<<n)-1```：将 ```zip``` 全部赋值为 $1$。 #### [模板题](https://www.luogu.com.cn/problem/P1171) 令 $dp_{i,zip}$ 表示为当前在第 $i$ 个节点，走过的状态为 ```zip```。 ```cpp #include<bits/stdc++.h> #define MAXN 21 using namespace std; int n,dis[MAXN][MAXN],dp[1<<20|1][MAXN]; inline int read(){ int res=0; char c=getchar(); while(!isdigit(c)){ c=getchar(); } while(isdigit(c)){ res=(res<<1)+(res<<3)+(c^48); c=getchar(); } return res; } inline void write(int x){ if(x>9){ write(x/10); } putchar(x%10+'0'); } int main(){ n=read(); for(register int i=1;i<=n;++i){ for(register int j=1;j<=n;++j){ dis[i][j]=read(); } } memset(dp,0x3f,sizeof(dp)); dp[1][1]=0; for(register int zip=1;zip<(1<<n);++zip){ for(register int i=1;i<=n;++i){ if(zip&(1<<(i-1))){ continue; } for(register int j=1;j<=n;++j){ if(!(zip&(1<<(j-1)))){ continue; } dp[zip|(1<<(i-1))][i]=min(dp[zip|(1<<(i-1))][i],dp[zip][j]+dis[j][i]); } } } int ans=INT_MAX; for(register int i=2;i<=n;++i){ ans=min(ans,dp[(1<<n)-1][i]+dis[i][1]); } write(ans); return 0; } ``` #### [例题](https://www.luogu.com.cn/problem/P1896) 令 $dp_{i,j,zip}$ 表示为选到第 $i$ 行，使用了 $j$ 个国王，第 $i$ 行的摆放状态为 ```zip```。 ```cpp #include<bits/stdc++.h> #define MAXN 2002 using namespace std; typedef long long ll; int cnt[MAXN],chk[MAXN]; ll dp[11][101][MAXN]; int main(){ int n,k,top=0; scanf("%d %d",&n,&k); for(int i=0;i<(1<<n);++i){ int x=i,sum=0; while(x){ if(x&1){ ++sum; } x>>=1; } cnt[i]=sum; if((((i<<1)|(i>>1))&i)==0){ chk[++top]=i; } } dp[0][0][0]=1; for(int i=1;i<=n;++i){ for(int l=1;l<=top;++l){ for(int r=1;r<=top;++r){ int x=chk[l],y=chk[r]; if(((y|(y<<1)|(y>>1))&x)==0){ for(int j=0;j<=k;++j){ if(j-cnt[x]>=0){ dp[i][j][x]+=dp[i-1][j-cnt[x]][y]; } } } } } } ll ans=0; for(int i=1;i<=top;++i){ ans+=dp[n][k][chk[i]]; } printf("%lld",ans); return 0; } ``` ## $\operatorname{Dp}$ 优化 ### 单调数据结构优化 通常来讲，如果一个 $\operatorname{Dp}$ 式子形如这样子： $$dp_i=\max_{i-len+1\le j\le i}\{dp_j+F(j)\}$$ 发现里面要求 $\operatorname{RMQ}$，即可使用单调队列进行优化。 #### [例题](https://www.luogu.com.cn/problem/P1776) 这就是前面背包板块所说的多重背包单调队列优化。 有 $dp$ 式： $$dp_{i}=\max_{0\le k\le c_i}\{dp_{i-k\times v_i}+k\times w_i\}$$ 令 $G_{x,y}=dp_{x\times v_i+y}$，则有： $$G_{x,y}=\max_{0\le k\le c_i}\{G_{x-k,y}\}+w_i\times x$$ 可能不太直观，这样子就好了。 $$G_{x,y}=\max_{x-c_i\le k\le c_i}\{G_{k,y}\}+w_i\times x$$ 长度为 $x$，右端点为 $c_i$ 的最大值，单调队列维护。 ```cpp #include<bits/stdc++.h> #define MAXN 40004 using namespace std; int dp[MAXN]; int main(){ int n,m,ans=0; scanf("%d %d",&n,&m); while(n--){ int w,v,sum; scanf("%d %d %d",&v,&w,&sum); if(!w){ ans+=v*sum; continue; } sum=min(sum,m/w); for(int i=0;i<w;++i){ deque<pair<int,int> > q; int part=(m-i)/w; for(int j=0;j<=part;++j){ while(!q.empty()&&dp[i+j*w]-j*v>=q.back().second){ q.pop_back(); } q.push_back(make_pair(j,dp[i+j*w]-j*v)); while(!q.empty()&&q.front().first<j-sum){ q.pop_front(); } dp[i+j*w]=max(dp[i+j*w],q.front().second+j*v); } } } printf("%d",ans+dp[m]); return 0; } ``` ### 数据结构（前缀后缀）优化 数据结构优化通常指使用数据结构维护 $dp$ 内容，$dp$ 每一次更新通过前面的查询操作得出，然后再修改该 $dp$ 值。 常见 $dp$ 式： $$dp_i=\max_{l\le j\le r}/\min_{l\le j\le r}\{dp_j\}+k$$ 对于这种，我们可以考虑把每一个 $dp$ 放进线段树，用线段树优化。 $$dp_i=\sum_{l\le i\le r}\{dp_j\}+k$$ 对于这种，我们采用树状数组或者线段树，更新操作即为区间查询，赋值操作即为单点修改。 前缀后缀优化指一个 $dp$ 式再前面数据结构优化的基础上，转移的内容按照一定顺序，例如 $dp_i$ 只能够从 $j\le i$ 转移过来，则只需要计算前缀 $\max$ 就可以了，优化了大部分数据结构优化的 $\log n$。 #### [例题](https://www.luogu.com.cn/problem/P1668) 很明显有 $dp$ 式： $$dp_i=\min_{i\in[l,r]}\{\min_{j\in{l,r}}\{dp_j\}\}+1$$ 发现一个区间的右端点才有贡献，所以考虑枚举每一只奶牛的右断电，有： $$dp_{r_i}=\min_{j\in[l_i-1,r_i-1]}\{dp_j\}+1$$ 所以考虑使用线段树维护动态区间 $\max$。 ```cpp #include<bits/stdc++.h> #define MAXT 1000010 #define MAXN 25010 #define INF 0x3f3f3f3f #define DEFAULT 1,0,t using namespace std; struct range{ int l,r; inline void get(){ scanf("%d %d",&l,&r); } inline friend bool operator<(const range &a,const range &b){ return a.r<b.r; } }cow[MAXN]; int n,t,dp[MAXT],tree[MAXT<<2]; inline void push_up(int root){ tree[root]=min(tree[root<<1],tree[root<<1|1]); } inline void build(int root,int l,int r){ if(l==r){ tree[root]=INF; return; } int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); push_up(root); } inline void change(int root,int l,int r,int pos,int val){ if(l==r){ tree[root]=val; return; } int mid=(l+r)>>1; if(pos<=mid){ change(root<<1,l,mid,pos,val); }else{ change(root<<1|1,mid+1,r,pos,val); } push_up(root); } inline int query(int root,int l,int r,int L,int R){ if(L<=l&&r<=R){ return tree[root]; } int mid=(l+r)>>1; if(mid<L){ return query(root<<1|1,mid+1,r,L,R); } if(mid>=R){ return query(root<<1,l,mid,L,R); } return min(query(root<<1,l,mid,L,R),query(root<<1|1,mid+1,r,L,R)); } inline void print(int root,int l,int r){ if(l==r){ printf("%d ",tree[root]); return; } int mid=(l+r)>>1; print(root<<1,l,mid); print(root<<1|1,mid+1,r); } int main(){ bool f=true; scanf("%d %d",&n,&t); build(DEFAULT); for(int i=1;i<=n;++i){ cow[i].get(); if(cow[i].l==1){ f=false; change(DEFAULT,cow[i].r,1); } } if(f){ puts("-1"); return 0; } // print(DEFAULT); // putchar('\n'); sort(cow+1,cow+1+n); for(int i=1;i<=n;++i){ change(DEFAULT,cow[i].r,min(query(DEFAULT,cow[i].r,cow[i].r),query(DEFAULT,cow[i].l-1,cow[i].r-1)+1)); // print(DEFAULT); // putchar('\n'); } int res=query(DEFAULT,t,t); printf("%d",(res^INF)?res:-1); return 0; } ``` ### 四边形不等式（决策单调性）优化 如果你有 $dp$ 式 $dp_i=\min_{1\le j\le i}w(j,i)$，并且 $w$ 满足四边形不等式 $a\le b\le c\le d$ 有 $w(a,b)+w(c,d)\ge w(a,c)+w(b,d)$，则可以使用四边形不等式优化。 很明显，令 $g(x)=dp_x$，则 $g$ 满足决策单调性：$i\le j$ 即 $g(i)\le g(j)$，证明如下： 令 $x\le y$，则有 $w(x,y)+w(0,0)\ge w(0,x)+w(0,y)$，即三角形不等式 $w(x,y)\ge w(0,x)+w(0,y)$。$w(i,i+1)\ge w(k,i)+(k,j)$ 当 $k\le i$ 时，证毕。 针对这一种单调性，我们通常使用 $cdq$ 分治解决。 分治利用了整体二分的思想，对于每一个 $dp_i$，$[l,mid]$ 一定小于等于 $dp_{mid}$；$[mid+1,r]$ 一定大于 $dp_{mid}$。所以我们把询问放在一起解决。 ```cpp inline int w(int l,int r); inline void cdq(int l,int r,int L,int R){ int mid=(l+r)>>1,T=L; for(int i=L+1;i<=min(R,mid);++i){ if(w(i,mid)<=w(T,mid)){ T=i; } } dp[mid]=w(T,mid); if(l<mid){ cdq(l,mid,L,T); } if(r>mid){ cdq(mid+1,r,T,R); } } ``` #### [例题](https://www.luogu.com.cn/problem/P3515) 令 $dp_i=\max_{1\le j<i}\{\sqrt{i-j}+a_j\}$，此处 $w(l,r)$ 应为 $\sqrt{r-l}$，证明显而易见。 ```cpp #include<bits/stdc++.h> #define MAXN 500005 using namespace std; int a[MAXN]; double sqr[MAXN],dp[MAXN]; inline double w(int i,int j){ return double(a[i])+sqr[abs(i-j)]; } void cdq(int l,int r,int kl,int kr){ if(l>r){ return; } int mid=(l+r)>>1,k; double ans=0; for(int i=kl;i<=min(mid,kr);++i){ if(w(i,mid)>ans){ ans=w(i,mid); k=i; } } dp[mid]=max(dp[mid],ans); cdq(l,mid-1,kl,k); cdq(mid+1,r,k,kr); } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); sqr[i]=sqrt(i); } cdq(1,n,1,n); reverse(a+1,a+1+n); reverse(dp+1,dp+1+n); cdq(1,n,1,n); for(int i=n;i>=1;--i){ printf("%d\n",int(ceil(dp[i]))-a[i]); } return 0; } ``` ### 斜率优化 最猎奇的优化。 如果有 $dp$ 式子如下： $$dp_i=\min_{1\le j<i}\{dp_j-k_i\times x_j\}$$ 令 $(x,dp_j)$ 为坐标轴上的点，$k$ 为斜率，则求之前的函数轴最小截距。 #### [例题](https://www.luogu.com.cn/problem/P3195) 由于斜率优化太猎奇了，主播还没有彻底掌握，等主播掌握之后再来讲解。 ### 矩阵快速幂优化 矩阵快速幂在基于矩阵乘法的结合律，通常适用于优化线性 $\operatorname{Dp}$。通常来讲，会有一个初始矩阵 $A$，里面有一个值表示 $dp$ 结果。你需要构造一个正方形矩阵 $C$ 使得 $A\times C$ 里面除了那个表示 $dp$ 的值，其他的和 $A$ 一致，并且乘法之后的结果要是 $dp$ 一轮之后的结果。 #### [模板题](https://www.luogu.com.cn/problem/CF226C) 直接来看[我的题解](https://www.luogu.com.cn/article/8c1ehdf5)。 #### [例题](https://www.luogu.com.cn/problem/P2106) 很容易可以得出令 $dp_{i,j}$ 表示第 $i$ 位填 $j$，就有： $$dp_{i,j}=\sum_{j-2\le k\le j+2}dp_{i-1,k}$$ 设计转移矩阵： ``` 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 ``` 设计初始矩阵： ``` 0 1 1 1 1 1 1 1 1 1 ``` ```cpp #include<cstdio> #include<vector> #define int long long #define mod 1000000007 using namespace std; typedef vector<vector<int>> matrix; inline matrix multi(matrix matrix1,matrix matrix2){ matrix result; result.resize(matrix1.size()); for(size_t first=1;first<matrix1.size();++first){ result[first].resize(matrix2.size()); for(size_t second=1;second<matrix2.size();++second){ for(size_t third=1;third<matrix2.size();++third){ (result[first][second]+=matrix1[first][third]*matrix2[third][second])%=mod; }; }; }; return result; }; inline matrix power(int base){ matrix matrix1; matrix1.resize(2); matrix1[1].resize(11); matrix1[1][2]=matrix1[1][3]=matrix1[1][4]=matrix1[1][5]=matrix1[1][6]=matrix1[1][7]=matrix1[1][8]=matrix1[1][9]=matrix1[1][10]=1; matrix matrix2; matrix2.resize(11); for(size_t first=1;first<=10;++first){ matrix2[first].resize(11); }; matrix2[1][1]=matrix2[1][2]=matrix2[1][3]=1; matrix2[2][1]=matrix2[2][2]=matrix2[2][3]=matrix2[2][4]=1; matrix2[3][1]=matrix2[3][2]=matrix2[3][3]=matrix2[3][4]=matrix2[3][5]=1; matrix2[4][2]=matrix2[4][3]=matrix2[4][4]=matrix2[4][5]=matrix2[4][6]=1; matrix2[5][3]=matrix2[5][4]=matrix2[5][5]=matrix2[5][6]=matrix2[5][7]=1; matrix2[6][4]=matrix2[6][5]=matrix2[6][6]=matrix2[6][7]=matrix2[6][8]=1; matrix2[7][5]=matrix2[7][6]=matrix2[7][7]=matrix2[7][8]=matrix2[7][9]=1; matrix2[8][6]=matrix2[8][7]=matrix2[8][8]=matrix2[8][9]=matrix2[8][10]=1; matrix2[9][7]=matrix2[9][8]=matrix2[9][9]=matrix2[9][10]=1; matrix2[10][8]=matrix2[10][9]=matrix2[10][10]=1; while(base){ if(base&1){ matrix1=multi(matrix1,matrix2); }; matrix2=multi(matrix2,matrix2); base>>=1; }; return matrix1; }; signed main(signed,char**){ int base; scanf("%lld",&base); if(base==1){ printf("10"); return 0; }; matrix result=power(base-1); int answer=0; for(size_t iter=1;iter<=10;++iter){ (answer+=result[1][iter])%=mod; }; printf("%lld",answer); return 0; }; ``` ## 后记 就由一张猎魔姐姐的图片收尾吧。 ![](https://cdn.luogu.com.cn/upload/image_hosting/ntf7rsj5.png)

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...