洛谷 P2279 [HNOI2003]消防局的设立

迈不过友情╰ 2023-08-17 17:49 104阅读 0赞

### 题意 ###

给出一个树，一个消防站能够覆盖与他距离小于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