DP 套 DP 学习笔记

简介

正常的 DP 是要满足若干条件，对某个东西求最值或者计数。但是某些情况下，求的东西可能刚好是相反的。即给定值反推有多少种条件能使得最后 DP 出的答案为给定的值。

将原来的 DP 作为内层，将内层 DP 每个状态的取值作为外层 DP 的状态，在下标上进行内层 DP 来转移外层 DP。

很多情况下要观察性质或搜索，将内层 DP 不可能取到的 DP 状态剪掉，或者合并内层 DP 的状态，以达到优化复杂度的目的。

例题

P8352 [SDOI/SXOI2022] 小 N 的独立集

简要题意

给定一个 $n$ 个点的树，已知每个点的权值在 $1\sim k$ 的范围内，对于每个 $x\in[1,kn]$ 求有多少种不同的点权使得这棵树的最大权独立集的权值为 $x$。$n\le 1000,k\le 5$。

解法

经典的树上最大权独立集求法。记 $h_{u,0/1}$ 分别表示以 $u$ 为根的子树中不选 $u$ 和选 $u$ 的最大权独立集。转移 $h_{u,0}=\sum\limits_{v\in son(u)}\max\{h_{v,0},h_{v,1}\},h_{u,1}=\sum\limits_{v\in son(u)}h_{v,0}$。

考虑计数，设 $f_{u,i,j}$ 表示在 $u$ 的子树内，$h_{u,0}$ 为 $i$，$h_{u,1}$ 为 $j$ 的方案数。记 $v\in son(u)$，容易得到 $f_{u,i+\max\{k,l\},j+k}=f_{u,i+\max\{k,l\},j+k}+f_{u,i,j}\times f_{v,k,l}$。不幸的是，这个 DP 仅状态就达到了 $O(n^3k^2)$。

考虑内层 DP 的无用状态。我们发现，$h_{u,1}-k\le h_{u,0}$，原因是在选 $u$ 的方案中删除点 $u$ 必然是一个合理的不选 $u$ 的方案。所以对于所有满足 $j-k>i$ 的 $h_{u,i,j}$ 的位置必然是 $0$。还有一个观察，即在 $i>j$ 时 DP 状态是冗余的，我们发现在此时转移时不需要关心 $j$ 的值，可以省去 $j$ 这一维。记 $f_{u,i,j}$ 表示在 $h_{u,0}$ 为 $i$，$\max\{0,h_{u,1}-h_{u,0}\}$ 为 $j$ 时的方案数。状态数成功的降到了 $O(n^2k^2)$。转移与上面的类似，可以通过，时间复杂度 $O(n^2k^4)$。同时判断某个状态是否为 $0$ 可以极大地加速。

Code

constexpr int N=1005,M=6;using ll=long long;constexpr ll mod=1e9+7;
int f[N][N*M][M],g[N*M][M],siz[N],n,t;
struct edge{int to,nxt;}e[N<<1];
int cnt=0,head[N];
inline void add(int u,int v)
{
    e[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}
inline void dfs(int u,int fa)
{
    siz[u]=1;
    for(int i=1;i<=t;i++)f[u][0][i]=1;
    for(int c=head[u];c;c=e[c].nxt)
    {
        int v=e[c].to;if(v==fa)continue;
        dfs(v,u);
        memcpy(g,f[u],sizeof(g));
        memset(f[u],0,sizeof(f[u]));
        for(int i=0;i<=siz[u]*t;i++)
            for(int j=0;j<=t;j++)
                if(g[i][j])
                    for(int k=0;k<=siz[v]*t;k++)
                        for(int l=0;l<=t;l++)
                            if(f[v][k][l])
                                f[u][i+k+l][max(j-l,0)]=(f[u][i+k+l][max(j-l,0)]+1ll*g[i][j]*f[v][k][l]%mod)%mod;
        siz[u]+=siz[v];
    }
}
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>t;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        add(u,v),add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=n*t;i++)
    {
        ll now=f[1][i][0];
        for(int j=1;j<=t;j++) if(i-j>=0) now+=f[1][i-j][j];
        cout<<now%mod<<"\n";
    }
}