这里列一点东西，以后继续补充。
- 更换枚举顺序，让一些不在dp式子左边的变量出现在最内层，方便接下来优化。
- （感觉非常常用）预处理后缀/前缀和，省去一些连续的枚举
- 删掉无用状态
- 树链剖分
CF1249F Maximum Weight Subset
题意
给你一棵树，有 $n$ 个节点，每个节点有点权 $a_i$。你需要选出若干个节点，满足任意两个之间距离（即简单路径上的边数）$\gt k$，求点权和的最大值。
思路
首先不难想到，我们可以设计一个状态 $f_{u,i}$ 表示 $u$ 子树中，$u$ 到最近一个选中的节点距离为 $i$，且子树中选中的节点距离 $\gt k$ 时，最大的权值和。
那么就直接按照这个思路来写一个转移。
int f[220][220],tmp[220];
void dfs(int u,int fa){
f[u][0]=a[u];
for(int v:g[u]){
if(v==fa)continue;
dfs(v,u);
// 从v到u，所有状态中的距离都要增加1
memcpy(tmp+1,f[v],219*4);
tmp[0]=0;
memcpy(f[v],tmp,220*4);
// 单走一边
for(int i=0;i<=n;++i)
tmp[i]=max(f[u][i],f[v][i]);
// 将v,u合并
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j)
if(i+j>k)tmp[min(i,j)]=max(tmp[min(i,j)],f[u][i]+f[v][j]);
}
memcpy(f[u],tmp,sizeof tmp);
}
}
可以发现这是 $\Theta(n^3)$ 的。
那么我们就可以开始优化啦。
先看第一条，我们的转移式子左边有一个 min(i,j)，这要求我们要枚举 $i,j$，不太舒服。所以可以直接枚举 $min(i,j)$ 的取值，然后选择让 $i$ 或者 $j$ 来 $=min(i,j)$。
int f[220][220],tmp[220];
void dfs(int u,int fa){
f[u][0]=a[u];
for(int v:g[u]){
if(v==fa)continue;
dfs(v,u);
// 从v到u，所有状态中的距离都要增加1
memcpy(tmp+1,f[v],219*4);
tmp[0]=0;
memcpy(f[v],tmp,220*4);
// 单走一边
for(int i=0;i<=n;++i)
tmp[i]=max(f[u][i],f[v][i]);
// 将v,u合并
for(int i=0;i<=n;++i){
- for(int j=0;j<=n;++j)
- if(i+j>k)tmp[min(i,j)]=max(tmp[min(i,j)],f[u][i]+f[v][j]);
+ for(int j=i;j<=n;++j){
+ if(i+j>k)tmp[i]=max(tmp[i],f[u][i]+f[v][j]);
+ if(i+j>k)tmp[i]=max(tmp[i],f[u][j]+f[v][i]);
+ }
}
memcpy(f[u],tmp,sizeof tmp);
}
}
注意到还有一个 if(i+j>k) 限制了 $j$ 的范围，我们考虑把它直接融入 for 中。
int f[220][220],tmp[220];
void dfs(int u,int fa){
f[u][0]=a[u];
for(int v:g[u]){
if(v==fa)continue;
dfs(v,u);
// 从v到u，所有状态中的距离都要增加1
memcpy(tmp+1,f[v],219*4);
tmp[0]=0;
memcpy(f[v],tmp,220*4);
// 单走一边
for(int i=0;i<=n;++i)
tmp[i]=max(f[u][i],f[v][i]);
// 将v,u合并
for(int i=0;i<=n;++i){
- for(int j=i;j<=n;++j){
- if(i+j>k)tmp[i]=max(tmp[i],f[u][i]+f[v][j]);
- if(i+j>k)tmp[i]=max(tmp[i],f[u][j]+f[v][i]);
+ for(int j=max(i,k-i+1);j<=n;++j){
+ tmp[i]=max(tmp[i],f[u][i]+f[v][j]);
+ tmp[i]=max(tmp[i],f[u][j]+f[v][i]);
}
}
memcpy(f[u],tmp,sizeof tmp);
}
}
好了，到此就达成了更换枚举顺序，让一些不在dp式子左边的变量出现在最内层，方便接下来优化。
那么接下来就可以考虑前缀/后缀和了。
我们直接把j这一层循环用后缀max处理掉。
int f[220][220],tmp[220],tmp1[220],tmp2[220];
void dfs(int u,int fa){
f[u][0]=a[u];
for(int v:g[u]){
if(v==fa)continue;
dfs(v,u);
// 从v到u，所有状态中的距离都要增加1
memcpy(tmp+1,f[v],219*4);
tmp[0]=0;
memcpy(f[v],tmp,220*4);
// 单走一边
for(int i=0;i<=n;++i)
tmp[i]=max(f[u][i],f[v][i]);
+ // 预处理后缀max
+ for(int i=n;i>=0;--i)
+ tmp1[i]=max(tmp1[i+1],f[u][i]),
+ tmp2[i]=max(tmp2[i+1],f[v][i]);
// 将v,u合并
for(int i=0;i<=n;++i){
- for(int j=max(i,k-i+1);j<=n;++j){
- tmp[i]=max(tmp[i],f[u][i]+f[v][j]);
- tmp[i]=max(tmp[i],f[u][j]+f[v][i]);
- }
+ tmp[i]=max(tmp[i],f[u][i]+tmp2[max(i,k-i+1)]);
+ tmp[i]=max(tmp[i],tmp1[max(i,k-i+1)]+f[v][i]);
}
memcpy(f[u],tmp,sizeof tmp);
}
}
这样就是 $\Theta(n^2)$ 的了。
进一步优化，我们需要找到是什么导致了 $\Theta(n^2)$。首先我们可以发现，之前的 memcpy 以及之后的转移我们都是以 $n$ 为上界的，但我们发现并不一定达到 $n$，只能达到 $maxdep$。所以可以先缩减一下范围。缩减完我们就发现这个其实是 $\Theta(n \log n)$ 的。
int f[220][220],tmp[220],tmp1[220],tmp2[220],dep[220];
void dfs(int u,int fa){
f[u][0]=a[u];
dep[u]=1;
for(int id=hd[u];id;id=ed[id].nxt){
int v=ed[id].to;
if(v==fa)continue;
dfs(v,u);
dep[v]++;
for(int i=dep[v];i>=1;--i)f[v][i]=f[v][i-1];
f[v][0]=0;
for(int i=0;i<=max(dep[u],dep[v]);++i)tmp[i]=max(f[u][i],f[v][i]);
tmp1[dep[u]+1]=tmp2[dep[v]+1]=0;
for(int i=dep[u];i>=0;--i)tmp1[i]=max(tmp1[i+1],f[u][i]);
for(int i=dep[v];i>=0;--i)tmp2[i]=max(tmp2[i+1],f[v][i]);
for(int i=0;i<=min(dep[u],dep[v]);++i){
if(max(i,k+1-i)<=dep[v])tmp[i]=max(tmp[i],f[u][i]+tmp2[max(i,k+1-i)]);
if(max(i,k+1-i)<=dep[u])tmp[i]=max(tmp[i],tmp1[max(i,k+1-i)]+f[v][i]);
}
memcpy(f[u],tmp,(max(dep[u],dep[v])+1)*4);
}
}
注意到我们的代码中出现了一个 min(dep[u],dep[v])，也就是说其实真正受影响的是 $[0,min(dep[u],dep[v])]$ 部分，而 $[min(dep[u],dep[v])+1,n]$ 则是直接继承过来的。那么联想到长链剖分的思想，我们可以将短儿子合并到长儿子，然后在长儿子头部插入一个 $0$。
插入操作，可以通过 deque.push_front 操作，或者将整个 $f[u]$ 倒置存放于 vector 直接 emplace_back。这里据说前者并不是非常 $\Theta(1)$，所以选择后一种实现方式。
int tmp[220],tmp1[220],tmp2[220],dep[220];
vector<int> F[220];int allo=0;
struct nbf{
int vid;
inline int& operator[] (int i){return F[vid][F[vid].size()-1-i];}
inline int operator[] (int i) const {return F[vid][F[vid].size()-1-i];}
inline void push_front(int x){F[vid].emplace_back(x);}
inline int front(){return F[vid].back();}
inline int size(){return F[vid].size();}
}f[220];
void dfs(int u,int fa){
dep[u]=1;
int mxid=-1;
for(int id=hd[u];id;id=ed[id].nxt){
int v=ed[id].to;
if(v==fa)continue;
dfs(v,u);
dep[v]++;
if(dep[v]>dep[u])dep[u]=dep[v],mxid=v;
}
if(mxid==-1){
f[u].vid=++allo;
}else{
f[u]=f[mxid];
}
f[u].push_front(max(a[u]+(f[u].size()>=k+1?f[u][k]:0),(f[u].size()?f[u].front():0)));
for(int id=hd[u];id;id=ed[id].nxt){
int v=ed[id].to;
if(v==fa||v==mxid)continue;
f[v].push_front(0);
nbf tmp=nbf{n+1};
F[n+1].assign(F[f[v].vid].begin(),F[f[v].vid].end());
for(int i=0;i<dep[v];++i)tmp[i]=max(tmp[i],f[u][i]);
for(int i=0;i<dep[v];++i){
int oi=max(i,k+1-i);
if(oi<dep[v])tmp[i]=max(tmp[i],f[u][i]+f[v][oi]);
if(oi<dep[u])tmp[i]=max(tmp[i],f[u][oi]+f[v][i]);
}
f[u][dep[v]-1]=tmp[dep[v]-1];
for(int i=dep[v]-2;i>=0;--i)f[u][i]=max(f[u][i+1],tmp[i]);
}
}
那么理论上就 $\Theta(n)$ 了吧。
收获
- 如果推出来一个复杂度很差的DP式子不要直接扔掉，可以先写一写，说不定能优化得非常棒。
- 树上的dp可以用合并/提升的角度来转移，从这个角度也能方便想到启发式合并的优化。
- 一般降低dp复杂度的方法都是将一部分内循环预处理。
- 简单题也不能简单写完就跑路了，还是得深入思考。