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

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}>\frac{a_r-a_l}{r-l} 时，我们需要更新 k。这样，每次更新 k 时，就会产生一个内部无法被 r 看到的区间，就能想到区间 DP。设 dp_{i,j} 表示想要看到 [i,j] 内全部亭子至少需要的守卫数量，不难想到，dp_{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{len}{2}},a_{\frac{len}{2}+1})；当区间长度为奇数，答案应该是 \max(\min(a_{\frac{len+1}{2}-1},a_{\frac{len+1}{2}}),\min(a_{\frac{len+1}{2}},a_{\frac{len+1}{2}+1}))。这时引入 k，用 dp_i 表示剩余 i 个胡萝卜的答案，很明显若 k 中有两个胡萝卜是左右各取一个，对中心点时没有影响的，所以是可以从 dp_{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] 邮局加强版设 dp_{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}]，拆开上面的式子即可证明，步骤略。所以由此可知 dp 满足四边形不等式关系，优化后复杂度 O(V^2+VP)。代码： 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 设 dp_u 表示以 u 为根的子树的方案数。对于 u 的两个儿子 x,y，合并它们要保证合并后两个序列相对有序，相当于把 siz_x 个数放在 siz_x+siz_y 个空的方案数量，即 C^{siz_x}_{siz_x+siz_y}=\frac{(siz_x+siz_y)!}{siz_x!siz_y!}，还要乘上 x,y 的拓扑序方案数 dp_x,dp_y，扩展到多个儿子就能得到： dp_u=\frac{(siz_u-1)!}{\prod_{v\in son(u)}siz_v!}\prod_{v\in son(u)}dp_v 暴力硬拆就能得到： dp_{rt}=n!\prod_{u=1}^{n} \frac{1}{siz_u} 做法 2：概率考虑枚举所有可能的排列，数量应该是 n!，而对于每个点而言，要是想要排列成立，该点对应的数字就应该是其子树中最小的，这样的概率应该是 \frac{1}{siz_u}，所以就能得到和上面一样的式子。没有题目，也没有代码。。。 P3177 [HAOI2015] 树上染色标准树形 DP 题。设 dp_{u,x} 表示 u 这棵子树内有 x 个黑点对答案产生的贡献，可以列出： dp_{u,x}=\max_{k} dp_{u,x-k}+dp_{v,k}+w*k*(m-k)+w*(siz_v-k)*(n-m-siz_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 这里求出每个点的 dfn 序，就可以把子树转化成一个连续的区间。对于节点 u = dfn_i，有三种转移：不选 u，跳过整个子树：f_{i + sz_u, j} \leftarrow \max(f_{i + sz_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…