DP 的效率取决于 \(3\) 方面：1. 状态总数 2. 每个状态的决策数 3. 状态转移计算量。这三方面都可以进行优化。
- 状态总数优化：相当于搜索的剪枝，去除无用状态；使用降维，设计 DP 状态时尽量使用低维的 DP。
- 决策数量优化：即状态转移方程的优化，减少决策数量，如斜率优化，四边形不等式优化。
- 状态转移计算量优化：如用预处理减少递推时间，用 Hash 表，线段树，树状数组等减少枚举时间。
一. 一般优化
几种基础的优化方式。
1. 倍增优化
动态规划是多阶段递推，可以使用倍增法将阶段性的线性增长加速为成倍增长。经典应用有 ST表，背包中的二进制拆分等。
2. 数据结构优化
如果题目与简单的区间操作有关，如区间查询，区间修改等，可以用线段树或者树状数组进行优化。把区间操作的复杂度优化到 \(O(\log n)\)，从而降低复杂度。
2.1 树状数组优化
例题 \(1\) P3287
首先注意到一个性质：对于在 \([L,R]\) 区间内加 \(1\) 的操作，将 \(R\) 设为 \(n\) 一定是最优的。因为：
-
如果 \(R \ne n\)，会导致 \(R\) 后面的数相对变小，不利于形成更长的单调不降序列。
-
如果 \(R=n\)，至少不会使单调不降序列变短。
令 \(f[i][j]\) 表示做过 \(j\) 次区间操作，每次操作起点不超过 \(i\)，且以 \(i\) 结尾的最长单调不降序列的最长长度，状态转移方程为：
\[f[i][j]=\displaystyle\max_{x<i,y\le j, a[x]+y \le a[i]+j}\{f[x][y]+1\} \]这是一个二维区间问题，可以使用二维树状数组进行优化。
#include<bits/stdc++.h>
using namespace std;
const int N=10009;
int n,k,ans,a[N],f[N][509],bit[509][5509];
int lsb(int x){return x&(-x);}
void update(int x,int y,int z){
for(int i=x;i<=k+1;i+=lsb(i)){
for(int j=y;j<=5500;j+=lsb(j)) bit[i][j]=max(bit[i][j],z);
}
}
int query(int x,int y){
int res=0;
for(int i=x;i;i-=lsb(i)){
for(int j=y;j;j-=lsb(j)) res=max(res,bit[i][j]);
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=k;j>=0;j--){
f[i][j]=query(j+1,a[i]+j)+1;
ans=max(ans,f[i][j]);
update(j+1,a[i]+j,f[i][j]);
}
}
cout<<ans;
return 0;
}
2.2. 线段树优化
例题 \(1\) P2605
定义 \(f[i][j]\) 为前 \(i\) 个基站中第 \(j\) 个基站建在 \(i\) 处的最小值，状态转移方程为：
\[f[i][j]=\displaystyle\min_{j-1\le k <i}\{f[k][j-1]+p[k][i]\} \]其中 \(p[k][i]\) 表示区间 \([k,i]\) 内没有被基站 \(i,k\) 覆盖的村庄的赔偿费用。
如果直接计算的话，需要 \(i,j,k\) 三重循环，复杂度 \(O(n^3)\)，如何优化？
-
滚动数组：发现 \(j\) 只与 \(j-1\) 有关，可以用滚动数组优化 \(j\) ，将复杂度降为 \(O(n^2)\)，优化后的状态转移方程：
\[f[i]=\displaystyle\min_{1\le k <i}\{dp[k]+p[k][i]\} \] -
区间操作的优化：方程中的 \(p\) 数组计算 \([i,k]\) 内的赔偿费用，是一个区间求和问题，用线段树优化。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200009;
const ll INF=0x3f3f3f3f3f3f3f3f;
int tot,head[N],nxt[N],to[N];
ll n,k,now,d[N],c[N],s[N],w[N],st[N],ed[N],f[N];
struct segment_tree{
int l,r;
ll val,tag;
}t[N*4];
void addedge(int x,int y){
nxt[++tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void init(){
n++,k++;
d[n]=INF;w[n]=INF;
for(int i=1;i<=n;i++){
st[i]=lower_bound(d+1,d+1+n,d[i]-s[i])-d;
ed[i]=lower_bound(d+1,d+1+n,d[i]+s[i])-d;
if(d[ed[i]]>d[i]+s[i]) ed[i]--;
addedge(ed[i],i);
}
}
void pushup(int p){
int ls=p*2,rs=p*2+1;
t[p].val=min(t[ls].val,t[rs].val);
}
void pushdown(int p){
int ls=p*2,rs=p*2+1;
if(t[p].tag){
t[ls].val+=t[p].tag;t[ls].tag+=t[p].tag;
t[rs].val+=t[p].tag;t[rs].tag+=t[p].tag;
t[p].tag=0;
}
}
void build(int p,int l,int r){
t[p].l=l;t[p].r=r;t[p].tag=0;
if(l==r){t[p].val=f[l];return ;}
int mid=l+(r-l)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
void update(int p,int L,int R,int c){
if(L>R) return ;
if(L<=t[p].l&&R>=t[p].r){t[p].val+=c;t[p].tag+=c;return ;}
pushdown(p);
int mid=t[p].l+(t[p].r-t[p].l)/2;
if(L<=mid) update(p*2,L,R,c);
if(R>mid) update(p*2+1,L,R,c);
pushup(p);
}
ll query(int p,int L,int R){
if(L>R) return INF;
if(L<=t[p].l&&R>=t[p].r) return t[p].val;
pushdown(p);
int mid=t[p].l+(t[p].r-t[p].l)/2;
ll res=INF;
if(L<=mid) res=min(res,query(p*2,L,R));
if(R>mid) res=min(res,query(p*2+1,L,R));
return res;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=2;i<=n;i++) cin>>d[i];
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n;i++) cin>>w[i];
init();
for(int i=1;i<=n;i++){
f[i]=now+c[i];
for(int j=head[i];j;j=nxt[j]){
int y=to[j];
now=now+w[y];
}
}
ll ans=f[n];
for(int i=2;i<=k;i++){
build(1,1,n);
for(int j=1;j<=n;j++){
f[j]=query(1,1,j-1)+c[j];
for(int k=head[j];k;k=nxt[k]){
int y=to[k];
update(1,1,st[y]-1,w[y]);
}
}
ans=min(ans,f[n]);
}
cout<<ans;
return 0;
}
二. 单调队列优化
2. 单调队列
顾名思义，单调队列的重点分为「单调」和「队列」。
「单调」指的是元素的「规律」——递增（或递减）。
「队列」指的是元素只能从队头和队尾进行操作。
2.1. 最大子序列之和
一个长度为 \(n\) 的整数序列 \(a\)，从中找出一个长度不超过 \(m\) 的连续子序列，使得该子序列中数的和最大。
定义 \(s[i]=\displaystyle\sum_{j=1}^ia[j]\)，那么连续子序列 \([l,r]\) 的和即为 \(s[r]-s[l-1]\)，原问题转化为：找出两个数 \(x,y\)，使得 \(s[y]-s[x]\) 最大且 \(y-x \leq m\)。
枚举右端点 \(i\)，当 \(i\) 固定时，找到左端点 \(j\)，使得 \(j \in [i-m,i-1]\) 且 \(s[j]\) 最小。
对于 \(j_2<j_1<i\) 且 \(s[j_2]>s[j_1]\) ，那么 \(s[j_2]\) 永远不会成为最优选择。因此答案集合一定是“下标位置递增，对应的 \(s\) 值也递增”的序列。这就是单调队列。
我们对每个 \(i\) 执行一下操作：
- 将队头每一个距离超过 \(m\) 的数值弹出
- 此时队头就是答案。
- 不断删除队尾，直到队尾对应的 \(s\) 值小于 \(s[i]\)，加入 \(i\)。
例题 \(1\) T331286
将工匠按照 \(s[i]\) 从小到大排序，可以按照顺序进行线性 DP。设 \(f[i][j]\) 表示第 \(i\) 个工匠刷前 \(j\) 块所能获得的最大报酬。
第 \(i\) 个工匠不刷：\(f[i][j]=f[i-1][j]\)。
第 \(j\) 块木板不刷：\(f[i][j]=f[i][j-1]\)。
如果第 \(i-1\) 个工匠刷第 \(k\) 块木板，则第 \(i\) 个工匠要刷第 \(k+1 \sim j\) 块木板，粉刷总数不超过 \(L_i\)，且必须粉刷 \(S_i\)。所以 \(k+1 \leq S_i \leq j\) 且 \(j-k \leq L_i\)。
\[f[i][j]=\displaystyle \max_{j-L_i\leq k \leq S_i-1}\{f[i-1][k]+P_i (j-k)\} \]可以把 \(i\) 看做定值，把 \(j,k\) 分为 \(2\) 项，那么状态转移方程整理为
\[f[i][j]=\displaystyle P_i·j+\max_{j-L_i\leq k \leq S_i-1}\{f[i-1][k]-P_i·k\} \]比较任意两个决策 \(k_1,k_2\)，满足 \(k_1<k_2<S_i\)。
\(k_1\) 一定会比 \(k_2\) 更早从 \([j-L_i,S_i-1]\) 里删除，那么如果 \(f[i-1][k_1]-P_i·k_1\) 小于 \(f[i-1][k_2]-P_i·k_2\)，那么 \(k_1\) 就比 \(k_2\) 更不优。
综上，可以维护一个 \(k_i\) 递增，\(f[i-1][k_i]-P_i·k_i\) 递减的单调队列。
整个算法的时间复杂度为 \(O(nm)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct worker{ll s,l,p;}w[109];
ll n,m,f[109][16009],q[16009];
bool cmp(const worker&a,const worker&b){return a.s<b.s;}
ll calc(ll i,ll k){return f[i-1][k]-w[i].p*k;}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(ll i=1;i<=m;i++) cin>>w[i].l>>w[i].p>>w[i].s;
sort(w+1,w+1+m,cmp);
for(ll i=1;i<=m;i++){
ll l=1,r=0;
for(ll k=max(0ll,w[i].s-w[i].l);k<=w[i].s-1;k++){
while(l<=r&&calc(i,q[r])<=calc(i,k)) r--;
q[++r]=k;
}
for(ll j=1;j<=n;j++){
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(j>=w[i].s){
while(l<=r&&q[l]<j-w[i].l) l++;
if(l<=r) f[i][j]=max(f[i][j],calc(i,q[l])+w[i].p*j);
}
}
}
cout<<f[m][n];
return 0;
}
例题 \(2\) T331284
设 \(f[i]\) 表示把前 \(i\) 个数分成若干段，在满足每段中所有的数和不超过 \(M\) 的前提下，各段的最大值之和最小是多少，状态转移方程：
\[f[i]=\displaystyle\min_{0\leq j <i ,\sum^i_{k=j+1}A_k\leq M}\bigg\{f[j]+\displaystyle\max_{j+1\leq k\leq i} A_k\bigg\} \]若采用枚举 \(j\) 的方法，复杂度是 \(O(n^2)\)，显然会超时，但 \(\displaystyle\max_{j+1\leq k\leq i} A_k\) 不容易用多项式表示，很难找到单调性。
基于“及时排除不可能的决策”，需要考虑一个决策 \(j\) 何时是可能出现的。
假设 \(j(0\leq j <i)\) 可能成为最优决策，是否可以通过邻项构造冲突性质。
设决策 \(j-1\) 优于 \(j\)，可知
\[f[j-1]+\displaystyle\max_{j\leq k\leq i} A_k \leq f[j]+\displaystyle\max_{j+1\leq k\leq i} A_k \]首先，既然上式成立，则 \(\displaystyle \sum_{k=j}^i A_k \leq M\)，其次，因为 \(f[j-1] \leq f[j]\)，所以可以假设 \(\displaystyle \max_{j\leq k \leq i}\{A_k\}=\displaystyle \max_{j+1\leq k \leq i}\{A_k\}\)，当且仅当 \(A_j<\displaystyle \max_{j\leq k \leq i}\{A_k\}\) 时成立。
如果上述两个命题同时成立，即 \(j-1\) 优于 \(j\)，如果向确保 \(j-1\) 不优于 \(j\)，则上述两性质不能同时成立。
所以，如果要确保 \(j(0 \leq j < i)\) 能成为最优决策，则除了 $ \displaystyle \sum ^i _{k=j+1}A[k] \leq m$ 外，还要满足以下两个性质中任意一个：
- \(\displaystyle \sum_{k=j}^i A[k]>m\)（即 \(j\) 是满足$\displaystyle \sum ^i_{k=j+1}A[k] \leq m $ 中最小的 \(j\)）
- \(A[j]=\displaystyle \max_{j \leq k \leq i} \{A[k]\}\)
如何维护这两个条件：
- 只需预处理出对于每个 \(i\)，满足 $\displaystyle \sum ^i_{k=j+1}A[k] \leq m $ 中最小的 \(j\)，即为 \(c[i]\)，在计算 \(f[i]\) 时对 \(c[i]\) 进行转移。
- 当一个新决策 \(j_2\) 进入候选集合时，若候选集合中有一个 \(j_1\) 满足 \(j_1<j_2\) 且 \(A[j_1] \leq A[j_2]\)，则 \(j_1\) 可悲排除。
综上所述，只需维护一个 \(j\) 单调递增， \(A_j\) 单调递减的队列，只有队列中的元素可能称为最优决策。
但转移方程中的 \(f[j]+\displaystyle\max_{j+1\leq k\leq i} A_k\) 没有单调性，不能取对头作为最优决策，而是要使用额外的数据结构（如 multiset），它与单调队列保存相同的候选集合，不过它以 \(f[j]+\displaystyle\max_{j+1\leq k\leq i} A_k\) 作为排序的一句，保证能快速查询最值。
最后，关于 \(\displaystyle\max_{j+1\leq k\leq i} A_k\) 有两种计算方式：
- 使用 ST 算法预处理，\(O(1)\) 查询。
- 单调队列中某一项的 \(\displaystyle\max_{j+1\leq k\leq i} A_k\) 的结果就是单调队列中下一个元素的 \(A\) 值。
时间复杂度为 \(O(n \log n)\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+9;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct node{
ll id,x,y;
bool operator<(const node&a)const{
return x+y>a.x+a.y;
}
};
ll n,m,lft=1,rght=0,q[N<<3],a[N],sum[N],lg[N],st[N][30],c[N],f[N];
bool vst[N];
priority_queue<node> qe;
void init(){
lg[1]=0;
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++) st[i][0]=a[i];
for(int i=1;i<=lg[n];i++){
for(int j=1;j<=(n-(1<<i)+1);j++){
st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
}
ll query(ll l,ll r){
ll len=lg[r-l+1];
return max(st[l][len],st[r-(1<<len)+1][len]);
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]>m){cout<<-1;return 0;}
sum[i]=sum[i-1]+a[i];
}
init();
c[0]=1;
for(int i=1;i<=n;i++){
for(int j=c[i-1];j<=n;j++){
if(sum[i]-sum[j-1]<=m){c[i]=j;break;}
}
}
for(int i=1;i<=n;i++){
f[i]=min(INF,f[c[i]-1]+query(c[i],i));
while(lft<=rght&&sum[i]-sum[q[lft]]>m){vst[q[lft]]=1;lft++;}
while(lft<=rght&&a[q[rght]]<a[i]){vst[q[rght]]=1;rght--;}
q[++rght]=i;
if(lft<rght) qe.push((node){q[rght-1],f[q[rght-1]],a[i]});
while(!qe.empty()&&(vst[qe.top().id]||qe.top().y<query(qe.top().id+1,i))) qe.pop();
if(!qe.empty()) f[i]=min(f[i],qe.top().x+qe.top().y);
}
cout<<f[n];
return 0;
}
总结
当状态转移方程形如 \(f[i]=\displaystyle\min_{L(i)<i<R(i)}\{f[i]+val(i,j)\}\)，且：
- 决策 \(j\) 的取值范围 \(L(i)\) 和 \(R(i)\) 是关于变量 \(i\) 的一次函数且具有单调性，即窗口长度保持不变。
- 优化的关键部分 \(val(i,j)\) 是关于变量 \(i\) 和 \(j\) 的多项式函数，
就可以使用单调队列进行优化。
一般而言，\(val(i,j)\) 至少可以分为两部分：
- 对于第一部分仅与 \(i\) 相关，无论采取哪个 \(j\)，第一部分均相等，这样可以选出最优决策后再累加。
- 对于第二部分仅与 \(j\) 相关，当 \(i\) 发生改变时不会发生变化，这样保证原来较优的决策能保持最有，这样可以保持单调队列的单调性，及时排除不可能的决策。