「NOI2008」奥运物流 - 树形动规+未来Dp | Bill Yang's Blog

「NOI2008」奥运物流 - 树形动规+未来Dp

题目大意



题目分析

首先,对于以$i$为根的树,通过方程的迭代,发现$R(i)$等于$\sum_xC_xk^{d(x,i)}$,其中$d(x,i)$表示$x$与$i$间的距离。
考虑一个三元环:

带入消元可得$R(1)=\frac{C_1+kC_2+k^2C_3}{1-k^3}$。
因此可得,$R(1)=\frac{\sum_xC_xk^{d(x,1)}}{1-k^{len}}$,其中$len$是环长。


因此,每个点$x$对$1$的贡献为$C_xk^{d(x,i)}k^{d(i,1)}=C_xk^{d(x,1)}$。
因此,我们不需将环和树分开考虑,忽略$1$的出边,直接考虑$1$的所有子树信息。
枚举环长$len$,显然$len$不可能增加,因此分母一定,我们只需要将分子最大化即可。
故我们需要最大化$\sum_{i=1}^nC_ik^{d(i,1)}$。

显然对于每次修改,一定直接将$x$的后继设置为$1$。
设$f[i,j]$表示在点$i$的子树中分配$j$次修改所得到的最大贡献和。

考虑到若在$x$点更新$x$点所有儿子的代价,也就是考虑儿子对自己的影响(原理类似后序遍历),那么分为两种情况:

  • 不修改$i$的后继,将$j$次修改分配到$i$子树中,再加上当前对$1$的贡献$C_ik^{d(i,1)}$。
  • 若修改$i$的后继,假设$d(i,1)=tmp$,那么子树的所有贡献值需要除以$k^{tmp-1}$,但若儿子也修改过,就不能修改其贡献值。

转移过程似乎有了后效性?
考虑思考对未来的影响从而消除后效性。

不妨将每次祖先的决策放在后代考虑,即祖先对儿子的决策造成影响(原理类似先序遍历,当然实现形式还是后序遍历,此题若写成记忆化搜索将会非常的爽)。
设$f[i,j,d]$表示在$i$的子树中分配$j$次修改,且$i$到$1$的距离为$d$的最大贡献和。

因为已经知道祖先到$1$的距离,因此可以在儿子处计算出贡献。
令$g[i,j,d]=\max\lbrace f[i,j,d+1],f[i,j,1]\rbrace$,因此我们可以转移状态:
若不修改$i$的后继:$f[i,j,d]=\max\lbrace {\sum_{son}g[son,t,d]}\rbrace+C_ik^d$。
若修改$i$的后继:$f[i,j,1]=\max\lbrace {\sum_{son}g[son,t,1]}\rbrace+C_ik$。
这两个转移可以用背包完成。

最后我们得出$1$的所有儿子的状态,再用一次背包转移即可得出分子的最大值,除以枚举的分母即可统计答案。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=65;
int n,m,suc[maxn];
double k,ans=0,c[maxn],f[maxn][maxn][maxn],g[maxn][maxn][maxn],h[maxn],Pow[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void TreeDp(int Now,int depth) {
for(int Next=2; Next<=n; Next++)
if(suc[Next]==Now)
TreeDp(Next,depth+1);
for(int d=min(2,depth); d<=depth; d++) { //不修改
memset(h,0,sizeof(h));
for(int Next=2; Next<=n; Next++)
if(suc[Next]==Now)
for(int j=m; j>=0; j--)
for(int k=j; k>=0; k--)
h[j]=max(h[j],h[k]+g[Next][j-k][d]);
for(int i=0; i<=m; i++)
f[Now][i][d]=h[i]+c[Now]*Pow[d];
}
if(depth>1) { //修改
memset(h,0,sizeof(h));
for(int Next=2; Next<=n; Next++)
if(suc[Next]==Now)
for(int j=m; j>=0; j--)
for(int k=j; k>=0; k--)
h[j]=max(h[j],h[k]+g[Next][j-k][1]);
for(int i=1; i<=m; i++)f[Now][i][1]=h[i-1]+c[Now]*k;
}
for(int i=0; i<=m; i++)
for(int d=0; d<depth; d++)
g[Now][i][d]=max(f[Now][i][d+1],f[Now][i][1]);
}
int main() {
n=Get_Int();
m=Get_Int();
scanf("%lf",&k);
for(int i=1; i<=n; i++)suc[i]=Get_Int();
for(int i=1; i<=n; i++)scanf("%lf",&c[i]);
Pow[0]=1;
for(int i=1; i<=n; i++)Pow[i]=Pow[i-1]*k;
for(int now=suc[1],len=2; now!=1; now=suc[now],len++) { //枚举环长
int tmp=suc[now];
suc[now]=1;
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int root=1; root<=n; root++)
if(suc[root]==1)TreeDp(root,1);
memset(h,0,sizeof(h));
for(int root=1; root<=n; root++)
if(suc[root]==1)
for(int j=m; j>=0; j--)
for(int k=j; k>=0; k--)
h[j]=max(h[j],h[k]+f[root][j-k][1]);
double Max=0;
for(int i=0; i<m; i++)Max=max(Max,h[i]);
if(tmp==1)Max=max(Max,h[m]); //整个环
ans=max(ans,(Max+c[1])/(1.0-Pow[len]));
suc[now]=tmp;
}
printf("%0.2lf",ans);
return 0;
}
本篇文章有用吗?有用还不快点击!
0%