目录
显示
题目链接
https://www.luogu.com.cn/problem/P4438
题解
设 \(f_{i,j,k}\) 表示对于 \(i\) 节点所在子树,从根节点到 \(i\) 经过 \(j\) 条未翻修公路,\(k\) 条未翻修公路时,整棵子树最小代价。
分两种情况讨论:
对于叶节点,我们枚举 \(j,k\),直接按题目中式子计算即可。
对于非叶子节点,我们枚举翻修铁路或公路,转移方程如下:
$$f_{i,j,k}=\min\{f_{ls,j+1,k}+f_{rs,j,k},f_{ls,j,k}+f_{rs,j,k+1}\}$$
#include <iostream> #include <algorithm> using namespace std; long long f[40005][45][45],a[20005],b[20005],c[20005]; int son[20005][2],n; void dfs(int u,int x,int y) { if(u>n) { u-=n; for(int i=0;i<=x;i++) for(int j=0;j<=y;j++) f[u+n][i][j]=c[u]*(a[u]+i)*(b[u]+j); return; } dfs(son[u][0],x+1,y); dfs(son[u][1],x,y+1); for(int i=0;i<=x;i++) for(int j=0;j<=y;j++) f[u][i][j]=min(f[son[u][0]][i+1][j]+f[son[u][1]][i][j],f[son[u][0]][i][j]+f[son[u][1]][i][j+1]); } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<n;i++) { cin>>son[i][0]>>son[i][1]; if(son[i][0]<0)son[i][0]=-son[i][0]+n; if(son[i][1]<0)son[i][1]=-son[i][1]+n; } for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]; dfs(1,0,0); cout<<f[1][0][0]<<endl; return 0; }