题目传送门
【题目大意】
有$n-1$个城市和$n$个乡村，它们构成一个二叉树。恰有一条公路和一条铁路通向每个城市，没有道路通向乡村，首都是编号为1的城市。每个乡村有三个参数$a,b,c$，每个乡村的不方便值为$c*(a+x)*(b+y)$，其中$x,y$分别代表这个乡村到首都要经过$x$条未修缮的公路和$y$条未修缮的铁路。对于每个城市，从通向它的两条路中选择一条修缮，求每个乡村的不方便值的最小总和。
【思路分析】
树形DP安排上
$f[x][i][j]$表示从$x$号节点到首都要经过$i$条未修缮的公路和$j$条未修缮的铁路，其子树中的所有乡村节点的不方便值之和。
如果$x$是乡村节点，那么直接枚举$i,j$求$f[x][i][j]=c[x]*(a[x]+i)*(b[x]+j)$
如果$x$是城市节点，那么枚举是修缮公路还是铁路，设$lson$是通过个公路到达的子节点，$rson$是通过铁路到达的子节点，转移方程为$f[x][i][j]=min(f[lson][i+1][j]+f[rson][i][j],f[lson][i][j]+f[rson][i][j+1])$
最后的答案就是$f[1][0][0]$
据说有方法可以优化一下空间？emmm有空再看叭QAQ
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define g() getchar() 8 #define rg register 9 #define go(i,a,b) for(rg int i=a;i<=b;i++) 10 #define back(i,a,b) for(rg int i=a;i>=b;i--) 11 #define db double 12 #define ll long long 13 #define il inline 14 #define pf printf 15 #define mem(a,b) memset(a,b,sizeof(a)) 16 using namespace std; 17 int fr(){ 18 int w=0,q=1; 19 char ch=g(); 20 while(ch<'0'||ch>'9'){ 21 if(ch=='-') q=-1; 22 ch=g(); 23 } 24 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 25 return w*q; 26 } 27 const int N=20002; 28 int n,m,ls[N],rs[N],a[N],b[N],c[N]; 29 ll f[N<<1][42][42]; 30 il void work(rg int x,rg int l,rg int r){ 31 //当前是x节点,到跟节点有l条公路,r条铁路 32 if(x>=n){ 33 rg int y=x-n+1; 34 go(i,0,l) go(j,0,r) f[x][i][j]=1ll*c[y]*(a[y]+i)*(b[y]+j); 35 //是乡村的话直接枚举统计就好啦 36 return; 37 } 38 if(ls[x]<0) ls[x]=-ls[x]+n-1,work(ls[x],l+1,r); 39 else work(ls[x],l+1,r); 40 if(rs[x]<0) rs[x]=-rs[x]+n-1,work(rs[x],l,r+1); 41 else work(rs[x],l,r+1); 42 go(i,0,l) go(j,0,r) f[x][i][j]=min(f[ls[x]][i+1][j]+f[rs[x]][i][j],f[rs[x]][i][j+1]+f[ls[x]][i][j]); 43 //如果是城市就选择修公路或者修铁路 44 return; 45 } 46 int main(){ 47 //freopen("","r",stdin); 48 //freopen("","w",stdout); 49 n=fr(); 50 go(i,1,n-1) ls[i]=fr(),rs[i]=fr(); 51 go(i,1,n) a[i]=fr(),b[i]=fr(),c[i]=fr(); 52 work(1,0,0); 53 pf("%lld\n",f[1][0][0]); 54 return 0; 55 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11589768.html
