区间 DP、树形 DP
P1880 [NOI1995] 石子合并
区间 DP 模板，代码：
#include<bits/stdc++.h>
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<=n;i++) cin>>a[i],a[i+n]=a[i];
for(int i=1;i<=(n<<1);i++) sum[i]=sum[i-1]+a[i],f[i][i]=0;
for(int len=2;len<=(n<<1);len++) for(int i=1;i<=(n<<1)-len+1;i++){
int j=i+len-1;
for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
}
for(int i=1;i<=n;i++) ans=min(ans,f[i][i+n-1]);
cout<<ans<<"\n";
ans=-1;
memset(f,0,sizeof f);
for(int len=2;len<=(n<<1);len++) for(int i=1;i<=(n<<1)-len+1;i++){
int j=i+len-1;
for(int k=i;k<j;k++) f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
}
for(int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]);
cout<<ans<<"\n";
return 0;
}P1063 [NOIP 2006 提高组] 能量项链
约等于板子了。。。
代码：
#include<bits/stdc++.h>
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<=n;i++) cin>>a[i],a[i+n+n]=a[i+n]=a[i];
for(int l=2;l<=n;l++) for(int i=1;i<=n*2-l+1;i++){
int j=i+l-1;
for(int k=i;k<j;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;i<=n;i++) ans=max(ans,dp[i][i+n-1]);
cout<<ans;
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$ 的两种情况取最优，每次扩展左端点更新对答案的贡献。
代码很短：
#include<bits/stdc++.h>
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<=n;i++) cin>>a[i];
for(int r=1;r<=n;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]));
}
}
cout<<ans;
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$ 的方法预处理一下，和转移取最大即可。
代码：
#include<bits/stdc++.h>
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<=n;i++){
cin>>a[i];
dp[1]=max(dp[1],a[i]);
}
for(int i=1;i<n;i++) ou[min(i,n-i)]=max(ou[min(i,n-i)],max(a[i],a[i+1]));
for(int i=2;i<n;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[i<<1]=max(dp[(i+1)<<1],ou[i]);
dp[i<<1|1]=max(dp[(i+1)<<1|1],ji[i]);
}
for(int i=n;i>=1;i--) cout<<dp[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<r$，求证 $w_{l,r+1}+w_{l+1,r}\ge w_{l,r}+w_{l+1,r+1}$。
根据 $w_{i,j}=a_i+a_{i+1}+...+a_{j}-(j-i+1)a[\frac{i+j}{2}]$，拆开上面的式子即可证明，步骤略。
所以由此可知 $dp$ 满足四边形不等式关系，优化后复杂度 $O(V^2+VP)$。
代码：
#include<bits/stdc++.h>
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<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for(int l=1;l<=n;l++){
w[l][l]=0;
for(int r=l+1;r<=n;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;j<=m;j++){
d[n+1][j]=n;
for(int i=n;i>=1;i--){
int mn=1e9,id;
for(int k=d[i][j-1];k<=d[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;
}
}
cout<<dp[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)
$$
代码：
#include<bits/stdc++.h>
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<node> 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<=min(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;i<n;i++){
cin>>u>>v>>w;
t[u].push_back({v,w});
t[v].push_back({u,w});
}
dfs(1,0);
cout<<dp[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)$
代码：
#include<bits/stdc++.h>
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<int> 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<=n;i++) cin>>fa,g[fa].push_back(i);
dfs(1);
for(int i=1;i<=n;i++) id[dfn[i]]=i;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1;i<=n+1;i++) for(int j=0;j<=k;j++) dp[i][j]=inf;
dp[1][0]=0;
for(int i=1;i<=n;i++) for(int j=0;j<=k;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+1<=k&&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;i<=k;i++) if(dp[n+1][i]>ans) ans=dp[n+1][i];
cout<<ans<<"\n";
return 0;
}
Comments NOTHING