养生网站模板,宜昌市做网站,酒店网络营销推广方式,动态站 网站地图怎么做题目链接#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id4557 题意概述#xff1a; 给出一棵树#xff0c;每个点付出代价w[i]可以控制距离和它不超过d的点#xff0c;现在给出一些点#xff0c;问控制这些点的最小代价是多少。 分析: 观察一下数据范围发现… 题目链接https://www.lydsy.com/JudgeOnline/problem.php?id4557 题意概述 给出一棵树每个点付出代价w[i]可以控制距离和它不超过d的点现在给出一些点问控制这些点的最小代价是多少。 分析: 观察一下数据范围发现算算法的复杂度可能和d有关。横看竖看这像是一个树形dp所以我们就把d搞到状态方程里面去嘛怎么就完全没有想到呢...... 既然要用树形dp就要先分析一下性质。 一个点如果被选择成为控制点那么它可以控制的点有子树中深度不超过d的点祖先中和它距离不超过d的点以及祖先的子树中的一些点。 感觉很麻烦的样子......因为对于那些祖先子树中的点控制的方向突然向上又向下了。 我们考虑到常用的技巧在树形dp中如果两个点会对答案产生贡献我们在其LCA处统计贡献。于是我们设两个dp方程 f(i,x)表示i点的子树中需要被控制的点全部被控制还可以向上控制x层的最小代价g(i,x)表示i点的子树中x层及以下需要被控制的点全部被控制的最小代价。 需要向上控制x层那么儿子中就需要有点可以向上控制x 1层的点被选择对于新来的子树j有两种情况一个是我们需要的点在这个新的子树中一个是我们需要的点在原来的子树中。 f(i,x)min(f(i,x)g(j,x),f(j,x1)g(i,x1)) init一开始把每点i当成孤点那么向上控制1~d层就只有靠自己f值初始化为w[i]f[i][0],g[i][0]根据这个点本身是否需要监视来判断。 但是注意答案在控制的长度恰好为x的时候不一定是最优的可能稍微控制的长度大一点答案反而更优于是把方程的意义改一下改成至少控制x层。 g(i,x)sum{g(j,x-1)|i-j},g(i,0)f(i,0) 小技巧怎么维护至少这个性质和看起来更劣的状态取min即可。 1 #includeiostream2 #includecstdio3 #includecstring4 #includecstdlib5 #includealgorithm6 #includecmath7 #includequeue8 #includeset9 #includemap
10 #includevector
11 #includecctype
12 #define inf 1e9
13 using namespace std;
14 const int maxn500005;
15 const int maxd25;
16
17 int N,D,M,W[maxn];
18 struct edge{ int to,next; }E[maxn1];
19 int first[maxn],np,f[maxn][maxd],g[maxn][maxd];
20 bool ob[maxn];
21
22 void _scanf(int x)
23 {
24 x0;
25 char chgetchar();
26 while(ch0||ch9) chgetchar();
27 while(ch0ch9) xx*10ch-0,chgetchar();
28 }
29 void add_edge(int u,int v)
30 {
31 E[np](edge){v,first[u]};
32 first[u]np;
33 }
34 void data_in()
35 {
36 _scanf(N);_scanf(D);
37 for(int i1;iN;i) _scanf(W[i]);
38 _scanf(M);
39 int x,y;
40 for(int i1;iM;i){
41 _scanf(x); ob[x]1;
42 }
43 for(int i1;iN;i){
44 _scanf(x);_scanf(y);
45 add_edge(x,y); add_edge(y,x);
46 }
47 }
48 void DFS(int i,int fa)
49 {
50 for(int d1;dD;d) f[i][d]W[i];
51 f[i][D1]inf;
52 if(ob[i]) f[i][0]g[i][0]W[i];
53 for(int pfirst[i];p;pE[p].next){
54 int jE[p].to;
55 if(jfa) continue;
56 DFS(j,i);
57 for(int d0;dD;d)
58 f[i][d]min(f[i][d]g[j][d],f[j][d1]g[i][d1]);
59 for(int dD;d0;d--) f[i][d]min(f[i][d],f[i][d1]);
60 g[i][0]f[i][0];
61 for(int d1;dD;d) g[i][d]g[j][d-1];
62 for(int d1;dD;d) g[i][d]min(g[i][d],g[i][d-1]);
63 }
64 }
65 void work()
66 {
67 DFS(1,0);
68 printf(%d\n,f[1][0]);
69 }
70 int main()
71 {
72 data_in();
73 work();
74 return 0;
75 } View Code 转载于:https://www.cnblogs.com/KKKorange/p/8678650.html
