ZR 集训 Day8 - 区间 DP、树形 DP

2026年7月24日 ooliver OI

ZR 集训 Day8 - 区间 DP、树形 DP

P1880 [NOI1995] 石子合并

区间 DP 模板，代码：

C++

#include
using namespace std;

const int N=205;
int n,ans=1e9;
int a[N],sum[N],f[N][N];

signed main(){
    memset(f,0x3f,sizeof f);
    cin>>n;
    for(int i=1;i>a[i],a[i+n]=a[i];
    for(int i=1;i

`#include
using namespace std;

const int N=205;
int n,ans=1e9;
int a[N],sum[N],f[N][N];

signed main(){
    memset(f,0x3f,sizeof f);
    cin>>n;
    for(int i=1;in;i++) cin>>a[i],a[i+n]=a[i];
    for(int i=1;i(n1);i++) sum[i]=sum[i-1]+a[i],f[i][i]=0;
    for(int len=2;len(n1);len++) for(int i=1;i(n1)-len+1;i++){
        int j=i+len-1;
        for(int k=i;kj;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
    }
    for(int i=1;in;i++) ans=min(ans,f[i][i+n-1]);
    coutans"\n";
    ans=-1;
    memset(f,0,sizeof f);
    for(int len=2;len(n1);len++) for(int i=1;i(n1)-len+1;i++){
        int j=i+len-1;
        for(int k=i;kj;k++) f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
    }
    for(int i=1;in;i++) ans=max(ans,f[i][i+n-1]);
    coutans"\n";
    return 0;
}`

P1063 [NOIP 2006 提高组] 能量项链

约等于板子了。。。

代码：

C++

#include
using namespace std;

const int N=305;
int n,ans;
int a[N],dp[N][N];

signed main(){
    cin>>n;
    for(int i=1;i>a[i],a[i+n+n]=a[i+n]=a[i];
    for(int l=2;l

`#include
using namespace std;

const int N=305;
int n,ans;
int a[N],dp[N][N];

signed main(){
    cin>>n;
    for(int i=1;in;i++) cin>>a[i],a[i+n+n]=a[i+n]=a[i];
    for(int l=2;ln;l++) for(int i=1;in*2-l+1;i++){
        int j=i+l-1;
        for(int k=i;kj;k++) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);
    }
    for(int i=1;in;i++) ans=max(ans,dp[i][i+n-1]);
    coutans;
    return 0;
}`

P4563 [JXOI2018] 守卫

考虑从左往右枚举右端点，并固定右端点，将左端点从右往左移。设 $l, r, k$ 分别为当前左端点、当前右端点、以及当前从右端点能看到的最左侧的亭子。

如下图所示，当 $\frac{a_{r} - a_{k}}{r - k} [PARSE ERROR: Ampersand] g t; \frac{a_{r} - a_{l}}{r - l}$ 时，我们需要更新 $k$ 。这样，每次更新 $k$ 时，就会产生一个内部无法被 $r$ 看到的区间，就能想到区间 DP。

设 $d p_{i, j}$ 表示想要看到 $[i, j]$ 内全部亭子至少需要的守卫数量，不难想到， $d p_{i, j}$ 至少为 $1$ ，因为至少要在右端点放一个守卫。

这样在更新 $k$ 时再加上区间的贡献即可。因为新的区间的右端点 $k$ 可以被 $r$ 看到，所以我们对区间包含 $k$ 和区间不包含 $k$ 的两种情况取最优，每次扩展左端点更新对答案的贡献。

代码很短：

C++

#include
using namespace std;

#define int long long
const int N=5e3+5;
int n,ans;
int a[N],dp[N][N];

signed main(){
    cin>>n;
    for(int i=1;i>a[i];
    for(int r=1;r=1;l--){
            if(!k||(a[r]-a[k])*(r-l)>(a[r]-a[l])*(r-k)) now+=min(dp[l+1][k],dp[l+1][k-1]),k=l;
            ans^=(dp[l][r]=now+min(dp[l][k],dp[l][k-1]));
        }
    }
    cout

`#include
using namespace std;

#define int long long
const int N=5e3+5;
int n,ans;
int a[N],dp[N][N];

signed main(){
    cin>>n;
    for(int i=1;in;i++) cin>>a[i];
    for(int r=1;rn;r++){
        ans^=(dp[r][r]=1);
        int k=0,now=1;
        for(int l=r-1;l>=1;l--){
            if(!k||(a[r]-a[k])*(r-l)>(a[r]-a[l])*(r-k)) now+=min(dp[l+1][k],dp[l+1][k-1]),k=l;
            ans^=(dp[l][r]=now+min(dp[l][k],dp[l][k-1]));
        }
    }
    coutans;
    return 0; 
}`

CF794E Choosing Carrot

考虑当 $k = 0$ 时，答案肯定在区间中间。因为一旦一个人想让中心点往一边偏移、使最终结果利于自己时，另一个人的策略一定是拿掉另一边的胡萝卜，所以最终答案一定在区间中间。

具体地，当区间长度为偶数，答案应该是 $\max (a_{\frac{l e n}{2}}, a_{\frac{l e n}{2} + 1})$ ；当区间长度为奇数，答案应该是 $\max (\min (a_{\frac{l e n + 1}{2} - 1}, a_{\frac{l e n + 1}{2}}), \min (a_{\frac{l e n + 1}{2}}, a_{\frac{l e n + 1}{2} + 1}))$ 。

这时引入 $k$ ，用 $d p_{i}$ 表示剩余 $i$ 个胡萝卜的答案，很明显若 $k$ 中有两个胡萝卜是左右各取一个，对中心点时没有影响的，所以是可以从 $d p_{i + 2}$ 转移过来的。若取了的所有胡萝卜都在一侧，那就按照 $k = 0$ 的方法预处理一下，和转移取最大即可。

代码：

C++

#include
using namespace std;

const int N=3e5+5;
int n;
int a[N],dp[N],ou[N],ji[N];

int main(){
    cin>>n;
    for(int i=1;i>a[i];
        dp[1]=max(dp[1],a[i]);
    }
    for(int i=1;i=1;i--){
        dp[i=1;i--) cout

`#include
using namespace std;

const int N=3e5+5;
int n;
int a[N],dp[N],ou[N],ji[N];

int main(){
    cin>>n;
    for(int i=1;in;i++){
        cin>>a[i];
        dp[1]=max(dp[1],a[i]);
    }
    for(int i=1;in;i++) ou[min(i,n-i)]=max(ou[min(i,n-i)],max(a[i],a[i+1]));
    for(int i=2;in;i++) ji[min(i-1,n-i)]=max(ji[min(i-1,n-i)],max(min(a[i-1],a[i]),min(a[i],a[i+1])));
    for(int i=n/2;i>=1;i--){
        dp[i1]=max(dp[(i+1)1],ou[i]);
        dp[i1|1]=max(dp[(i+1)1|1],ji[i]);
    }
    for(int i=n;i>=1;i--) coutdp[i]" ";
    return 0;
}`

P4767 [IOI 2000] 邮局加强版

设 $d p_{i, j}$ 表示前 $i$ 个村庄放 $j$ 个邮局的最短距离， $w_{i, j}$ 表示区间 $[i, j]$ 内放一个邮局的最短距离，得到状态转移方程：

$\begin{aligned} w_{i,j}&=w_{i,j-1}+a_j-a_{\frac{i+j}{2}},j>i \\ dp_{i,j}&=\min\{dp_{k,j-1}+w_{k+1,i}\} ,k\in[0,i) \\ \end{aligned}$

这个转移看上去就是可以四边形不等式搞一下的，根据四边形不等式，我们需要证明 $w$ 拥有区间包含单调性并同时满足四边形不等式关系。

先说区间包含单调性，我们可以感性证明一下：区间变大，所需距离肯定变大，证毕。

再说 $w$ 是否满足四边形不等式关系，也就是这个问题：

有 $l根据 $w_{i, j} = a_{i} + a_{i + 1} + . . . + a_{j} - (j - i + 1) a [\frac{i + j}{2}]$ ，拆开上面的式子即可证明，步骤略。

所以由此可知 $d p$ 满足四边形不等式关系，优化后复杂度 $O (V^{2} + V P)$ 。

代码：

C++

#include
using namespace std;

const int N=3e3+5;
int n,m;
int a[N],dp[N][N],w[N][N],d[N][N];

signed main(){
    cin>>n>>m;
    for(int i=1;i>a[i];
    sort(a+1,a+1+n);
    for(int l=1;l>1];
    }
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for(int j=1;j=1;i--){
            int mn=1e9,id;
            for(int k=d[i][j-1];k

`#include
using namespace std;

const int N=3e3+5;
int n,m;
int a[N],dp[N][N],w[N][N],d[N][N];

signed main(){
    cin>>n>>m;
    for(int i=1;in;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int l=1;ln;l++){
        w[l][l]=0;
        for(int r=l+1;rn;r++) w[l][r]=w[l][r-1]+a[r]-a[(l+r)>>1];
    }
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for(int j=1;jm;j++){
        d[n+1][j]=n;
        for(int i=n;i>=1;i--){
            int mn=1e9,id;
            for(int k=d[i][j-1];kd[i+1][j];k++)
                if(dp[k][j-1]+w[k+1][i]mn) 
                    mn=dp[k][j-1]+w[k+1][i],id=k;
            dp[i][j]=mn,d[i][j]=id;
        }
    }
    coutdp[n][m];
    return 0;
}`

树上拓扑序方案数

给一棵有根树 $T = (V, E)$ ，求拓扑序方案数。

做法 1：树形 DP

设 $d p_{u}$ 表示以 $u$ 为根的子树的方案数。

对于 $u$ 的两个儿子 $x, y$ ，合并它们要保证合并后两个序列相对有序，相当于把 $s i z_{x}$ 个数放在 $s i z_{x} + s i z_{y}$ 个空的方案数量，即 $C^{{s i z_{x}}_{s i z_{x} + s i z_{y}}} = \frac{(s i z_{x} + s i z_{y})!}{s i z_{x}! s i z_{y}!}$ ，还要乘上 $x, y$ 的拓扑序方案数 $d p_{x}, d p_{y}$ ，扩展到多个儿子就能得到：

$d p_{u} = \frac{(s i z_{u} - 1)!}{\prod_{v \in s o n (u)} s i z_{v}!} \prod_{v \in s o n (u)} d p_{v}$

暴力硬拆就能得到：

$d p_{r t} = n! \prod_{u = 1}^{n} \frac{1}{s i z_{u}}$

做法 2：概率

考虑枚举所有可能的排列，数量应该是 $n!$ ，而对于每个点而言，要是想要排列成立，该点对应的数字就应该是其子树中最小的，这样的概率应该是 $\frac{1}{s i z_{u}}$ ，所以就能得到和上面一样的式子。

没有题目，也没有代码。。。

P3177 [HAOI2015] 树上染色

标准树形 DP 题。

设 $d p_{u, x}$ 表示 $u$ 这棵子树内有 $x$ 个黑点对答案产生的贡献，可以列出：

$d p_{u, x} = \max_{k} d p_{u, x - k} + d p_{v, k} + w * k * (m - k) + w * (s i z_{v} - k) * (n - m - s i z_{v} + k)$

代码：

C++

#include
using namespace std;
#define int long long

const int N=2e3+5;
int n,k;
int dp[N][N],siz[N];
struct node{
    int v,w;
};
vector t[N];

void dfs(int x,int fa){
    siz[x]=1;
    for(auto [v,w]:t[x]){
        if(v==fa) continue;
        dfs(v,x);
        siz[x]+=siz[v];
        for(int i=min(k,siz[x]);i>=0;i--)
            for(int j=max(i-siz[x]+siz[v],0ll);j>n>>k;
    for(int i=1,u,v,w;i>u>>v>>w;
        t[u].push_back({v,w});
        t[v].push_back({u,w});
    }
    dfs(1,0);
    cout

`#include
using namespace std;
#define int long long

const int N=2e3+5;
int n,k;
int dp[N][N],siz[N];
struct node{
    int v,w;
};
vectornode> t[N];

void dfs(int x,int fa){
    siz[x]=1;
    for(auto [v,w]:t[x]){
        if(v==fa) continue;
        dfs(v,x);
        siz[x]+=siz[v];
        for(int i=min(k,siz[x]);i>=0;i--)
            for(int j=max(i-siz[x]+siz[v],0ll);jmin(i,siz[v]);j++)
                dp[x][i]=max(dp[x][i],dp[x][i-j]+dp[v][j]+1ll*j*(k-j)*w+1ll*(siz[v]-j)*(n-k-siz[v]+j)*w);
    }
}

signed main(){
    cin>>n>>k;
    for(int i=1,u,v,w;in;i++){
        cin>>u>>v>>w;
        t[u].push_back({v,w});
        t[v].push_back({u,w});
    }
    dfs(1,0);
    coutdp[1][k];
    return 0;
}`

P12444 [COTS 2025] 发好奖 / Hijerarhija

这里求出每个点的 $d f n$ 序，就可以把子树转化成一个连续的区间。

对于节点 $u = d f n_{i}$ ，有三种转移：

不选 $u$ ，跳过整个子树： $f_{i + s z_{u}, j} \leftarrow \max (f_{i + s z_{u}, j}, f_{i, j})$
选 $u$ ，花费 $1$ 的代价： $f_{i + 1, j + 1} \leftarrow \max (f_{i + 1, j + 1}, f_{i, j})$
选 $u$ ，花费代价 $c_{u}$ ，获得价值 $p_{u}$ ： $f_{i + 1, j + c_{u}} \leftarrow \max (f_{i + 1, j + c_{u}}, f_{i, j} + p_{u})$

代码：

C++

#include
using namespace std;

const int N=5e3+5,inf=-2e9;
int n,k,idx;
int dfn[N],id[N],sz[N],c[N],p[N],dp[N][N];
vector g[N];

void dfs(int u){
    dfn[u]=++idx,sz[u]=1;
    for(int v:g[u]) dfs(v),sz[u]+=sz[v];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=2,fa;i>fa,g[fa].push_back(i);
    dfs(1);
    for(int i=1;i>p[i];
    for(int i=1;i>c[i];
    for(int i=1;ians) ans=dp[n+1][i];
    cout

`#include
using namespace std;

const int N=5e3+5,inf=-2e9;
int n,k,idx;
int dfn[N],id[N],sz[N],c[N],p[N],dp[N][N];
vectorint> g[N];

void dfs(int u){
    dfn[u]=++idx,sz[u]=1;
    for(int v:g[u]) dfs(v),sz[u]+=sz[v];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=2,fa;in;i++) cin>>fa,g[fa].push_back(i);
    dfs(1);
    for(int i=1;in;i++) id[dfn[i]]=i;
    for(int i=1;in;i++) cin>>p[i];
    for(int i=1;in;i++) cin>>c[i];
    for(int i=1;in+1;i++) for(int j=0;jk;j++) dp[i][j]=inf;
    dp[1][0]=0;
    for(int i=1;in;i++) for(int j=0;jk;j++){
        if(dp[i][j]==inf) continue;
        int u=id[i];
        if(dp[i+sz[u]][j]dp[i][j]) dp[i+sz[u]][j]=dp[i][j];
        if(j+1k&&dp[i+1][j+1]dp[i][j]) dp[i+1][j+1]=dp[i][j];
        if(j+c[u]k&&dp[i+1][j+c[u]]dp[i][j]+p[u]) dp[i+1][j+c[u]]=dp[i][j]+p[u];
    }
    int ans=0;
    for(int i=0;ik;i++) if(dp[n+1][i]>ans) ans=dp[n+1][i];
    coutans"\n";
    return 0;
}`

ZR 集训 Day8 - 区间 DP、树形 DP

P1880 [NOI1995] 石子合并

P1063 [NOIP 2006 提高组] 能量项链

P4563 [JXOI2018] 守卫

CF794E Choosing Carrot

P4767 [IOI 2000] 邮局 加强版

树上拓扑序方案数

做法 1：树形 DP

做法 2：概率

P3177 [HAOI2015] 树上染色

P12444 [COTS 2025] 发好奖 / Hijerarhija

P4767 [IOI 2000] 邮局加强版