给出一个树，一个消防站能够覆盖与他距离小于2的点。
求覆盖整个树需要多少个消防站。
有贪心思路和动规思路，这篇题解使用动规。
所以按照树形DP的常规套路，我们把一棵子树的状态作为一个划分状态的标准。但是一个子树可能还可以向外覆盖点，也有可能有几个点没覆盖。
由于覆盖半径是2，对于一棵子树划分5种状态：
\(f_{i,0}\)向上覆盖2个。
\(f_{i,1}\)向上覆盖1个。
\(f_{i,2}\)正好覆盖完子树。
\(f_{i,3}\)覆盖完儿子。
\(f_{i,4}\)覆盖完孙子。
需要的消防局数目。
\(f_{i,0}\)选了自己，所以孙子会被覆盖到。要求曾孙全部被覆盖，儿子0-4的状态都满足。
\[f_{i,0}=1+\min(f_{i.child,[0,4]})\]
\(f_{i,1}\)选了儿子中的一个节点，所以其他儿子也会被覆盖到。但是其他儿子的儿子 无法被覆盖到。所以在转移时，随机选取一个点放消防站，并要求其他点的儿子被覆盖到。
\[f_{i,1}=\min(\min (f_{i.child,[0,3]})_{i.child!=k}+f_{k,0} )_{k\in \{i.child\}}\]
同理有
\[f_{i,2}=\min(\min (f_{i.child,[0,2]})_{i.child!=k}+f_{k,1} )_{k\in \{i.child\}}\]
要让根节点的儿子都被覆盖，就是让它们本身都覆盖（好zz啊）
\[f_{i,3}=\sum(f_{i.child,[0,2]})\]
同理有
\[f_{i,4}=\sum(f_{i.child,[0,3]})\]
取[0,2]的最小值，就是覆盖自身时的答案。
对于状态0，[0,4]中显然4最优
\[f_{i,0}=1+\min(f_{i.child,4})\]
同理有
\[f_{i,3}=\sum(f_{i.child,2})\]
\[f_{i,4}=\sum(f_{i.child,3})\]
此时0，3和4的状态处理完成，可以利用它们优化1和2的转移。
状态1，可以让所有孙子被覆盖，然后取\(f_{i.child,0}-f_{i.child,3}\)的最小值。这个式子相当于覆盖与i相邻的点需要的消防站数目。
所以有
\[f_{i,1}=\min (f_{i.child,0}-f_{i.child,3})+f_{i,4}\]
同理有
\[f_{i,2}=\min (f_{i.child,2}-f_{i.child,1})+f_{i,3}\]
别看了，很丑，还是抄的。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int MAXN=1005; int n,ne,head[MAXN],cnt,temp,temp1,temp2; int f[MAXN][5]; bool tree[MAXN][MAXN]; int main() { scanf("%d",&n); for(int i=2;i<=n;i++) { int x; scanf("%d",&x); tree[x][i]=1; } for(int i=n;i>=1;i--) { f[i][0]=1; temp1=1919,temp2=1919; for(int p=1;p<=n;p++) { if(tree[i][p]) { f[i][3]+=f[p][2]; f[i][4]+=f[p][3]; f[i][0]+=f[p][4]; temp1=min(temp1,f[p][0]-f[p][3]); temp2=min(temp2,f[p][1]-f[p][2]); } } f[i][1]=f[i][4]+temp1; f[i][2]=min(f[i][3]+temp2,min(f[i][0],f[i][1])); f[i][3]=min(f[i][2],f[i][3]); f[i][4]=min(f[i][4],f[i][3]);; } printf("%d",f[1][2]); return 0; }转载于:https://www.cnblogs.com/ehznehc/p/11372148.html
相关资源：JAVA上百实例源码以及开源项目