题解：AT_ndpc2026_f 集合

manboo · 2026-05-07 13:19:27 · 题解

前置芝士：笛卡尔树、树形 dp。

根据笛卡尔树的定义，显然按照 p 数组大小构建笛卡尔树后，如果选择点 x,y，那么必须选择 \operatorname{lca}\left(x,y\right)。

考虑树形 dp，设 f_{x,k} 表示在以点 x 为根节点的子树里选择 k 个点的最小成本，初值必然为 f_{x,0}=0。

令笛卡尔树里，点 x 的左右儿子分别为 ls,rs，枚举以 ls 为根节点的子树（以下简称为左子树）里选择了 i 个点，以 rs 为根节点的子树（以下简称为右子树）里选择了 j 个点，则：

左右子树都选：此时 i,j\ge1，必须要选择根节点 x，因此共选择了 i+j+1 个点，有 f_{x,i+j+1}=\min\left(f_{x,i+j+1},f_{ls,i}+f_{rs,j}+a_x\right)。
只选左子树：此时 i\ge1,j=0，可以选择要或不要根节点 x，因此有两种情况：
- 选择要根节点：共选择了 i+1 个点，有 f_{x,i+1}=\min\left(f_{x,i+1},f_{ls,i}+a_x\right)。由于 j=0，这与 f_{x,i+j+1}=\min\left(f_{x,i+j+1},f_{ls,i}+f_{rs,j}+a_x\right) 是等价的。
- 选择不要根节点：共选择了 i 个点，有 f_{x,i}=\min\left(f_{x,i},f_{ls,i}\right)。
只选右子树：此时 j\ge1,i=0，可以选择要或不要根节点 x，因此有两种情况：
- 选择要根节点：共选择了 j+1 个点，有 f_{x,j+1}=\min\left(f_{x,j+1},f_{rs,j}+a_x\right)。由于 i=0，这与 f_{x,i+j+1}=\min\left(f_{x,i+j+1},f_{ls,i}+f_{rs,j}+a_x\right) 是等价的。
- 选择不要根节点：共选择了 j 个点，有 f_{x,j}=\min\left(f_{x,j},f_{rs,j}\right)。

发现这五个转移方程是可以合并成三个的，得到最终转移方程：

\begin{cases}f_{x,i+j+1}=\min\left(f_{x,i+j+1},f_{ls,i}+f_{rs,j}+a_x\right)\\f_{x,i}=\min\left(f_{x,i},f_{ls,i}\right)\\f_{x,j}=\min\left(f_{x,j},f_{rs,j}\right)\end{cases}

剩下的就是树形 dp 板子了，上代码：

const int N=5001;
int n,p[N],a[N],sz[N],ls[N],rs[N];
long long ans[N],f[N][N];
void dfs(int x)
{
    f[x][0]=0,sz[x]=1;
    if(ls[x]) dfs(ls[x]),sz[x]+=sz[ls[x]];
    if(rs[x]) dfs(rs[x]),sz[x]+=sz[rs[x]];
    for(int i=0;i<=sz[ls[x]];i++)
    {
        for(int j=0;j<=sz[rs[x]];j++)
        {
            f[x][i+j+1]=min(f[x][i+j+1],f[ls[x]][i]+f[rs[x]][j]+a[x]);
            f[x][i]=min(f[x][i],f[ls[x]][i]);
            f[x][j]=min(f[x][j],f[rs[x]][j]);
        }
    }
    for(int i=1;i<=sz[x];i++) ans[i]=min(ans[i],f[x][i]);
}
int top,st[N];
inline void solve()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        p[i]=read(),ls[i]=rs[i]=0,ans[i]=1e18;
        for(int j=0;j<=n;j++) f[i][j]=1e18;
    }
    for(int i=1;i<=n;i++) a[i]=read();
    top=0;
    for(int i=1,k=0;i<=n;i++)
    {
        k=top;
        while(k&&p[st[k]]>p[i]) k--;
        if(k<top) ls[i]=st[k+1];
        if(k) rs[st[k]]=i;
        st[++k]=i,top=k;
    }  //构建笛卡尔树 
    dfs(st[1]);  //笛卡尔树通常以栈底为根节点 
    for(int i=1;i<n;i++) print(ans[i]),putchar(' ');
    print(ans[n]),putchar('\n');
}
int main()
{
    for(int T=read();T;T--) solve();
    return 0;
}

制作不易，点个赞吧，求求了！