考察:树形dp
这道题战略游戏要求看到所有的边,本题要求看到所有的点
没想出来,参考了大佬的思路
照搬大佬的思路:
设树上某点u能被看见,这个点要么自己安插士兵,要么父节点安插士兵,要么子节点安插士兵.设f[u,st]表示u的st状态的最小花费.st==0时,它u被父节点看见,st==1,u被子节点看见,st==2时,u自己安插了士兵.
根据以上可以写出转移方程(由子节点推父节点):
f[u,0] += min(f[v][1],f[v][2])(v是u的子节点,v要么被自己的子节点看见,要么自己就安插了士兵)
f[u,1] += min(f[k][2]+min(f[v][1],f[v][2])(k是自己安插士兵的花费最小的子节点,而v是其他子节点)
f[u,2] += min(f[v][1],f[v][2],f[v][0])(三种都有可能)
注意:由所有子节点的情况推出父节点,因为父节点需要所有子节点情况成立才成立.
但是这道题需要求出的是f[v][2]-min(f[v][1],f[v][2])的最小值,如果直接求f[v][2]的最小值会WA.关于原因这里有详细证明 GO
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <algorithm>
5 using namespace std;
6 const int N = 1510,INF = 0x3f3f3f3f;
7 int h[N],w[N],idx;
8 int f[N][3];
9 bool has_fa[N];
10 struct Road{
11 int fr,to,ne;
12 }road[N*N>>1];
13 void add(int a,int b)
14 {
15 road[idx].to = b,road[idx].fr = a,road[idx].ne = h[a],h[a] = idx++;
16 }
17 void dfs(int u)
18 {
19 int res = INF;
20 f[u][2]+=w[u];
21 f[u][1] = INF;
22 for(int i=h[u];i!=-1;i=road[i].ne)
23 {
24 int v = road[i].to;
25 dfs(v);
26 f[u][0] += min(f[v][1],f[v][2]);
27 f[u][2] += min(f[v][1],min(f[v][2],f[v][0]));
28 //if(f[v][2]<minv) minv = f[v][2],t = min(f[v][1],f[v][2]);
29 res = min(f[v][2]-min(f[v][1],f[v][2]),res);
30 }
31 if(res<INF) f[u][1]=min(f[u][0]+res,f[u][1]);
32 }
33 int main()
34 {
35 int n,root = 1;
36 scanf("%d",&n);
37 memset(h,-1,sizeof h);
38 for(int i=1;i<=n;i++)
39 {
40 int x,t,m; scanf("%d%d%d",&x,&t,&m);
41 w[x] = t;
42 while(m--)
43 {
44 int v; scanf("%d",&v);
45 add(x,v);
46 has_fa[v] = 1;
47 }
48 }
49 while(has_fa[root]) root++;
50 dfs(root);
51 printf("%d\n",min(f[root][1],f[root][2]));
52 return 0;
53 }