本文主要是介绍洛谷 P2279 [HNOI2003] 消防局的设立，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：
和“战略游戏”很像，但是状态明显变多了。
dp[i][0]代表i节点向上覆盖至i的父亲的父亲。
dp[i][1]代表i结点向上覆盖至i的父亲。
dp[i][2]代表i结点覆盖自身
dp[i][3]代表i结点向下覆盖自己的儿子。
dp[i][4]代表i结点向下覆盖自己的孙子。
状态方程大家可以看洛谷中的题解，这里不过多浪费时间了，给出一个参考代码，逻辑会稍微清晰一点。
代码有注释：
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_map>
#include<set>
#define int long long
#define MAX 2000
#define inf 0x3f3f3f3f
#define _for(i,a,b) for(int i=a;i<(b);i++)
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts;
int dx[] = { 0,1,0,-1};
int dy[] = { 1,0,-1,0 };
vector<int>vec[MAX];
int dp[MAX][5];//五个状态
void dfs(int u) {dp[u][0] = 1;//由于这个状态必须选择本身作为消防站，并且自己选中之后，其他儿子的状态不必要考虑，因为已经覆盖了祖先了。dp[u][3] = 0;dp[u][4] = 0;for (int i = 0; i < vec[u].size(); i++) {//遍历儿子结点int son = vec[u][i];dfs(son);dp[u][0] += dp[son][4];//其他儿子的状态，状态需要取4，因为是需要取最小值，其他状态覆盖过多会使消防站重复dp[u][3] += dp[son][2];//同理，因为是向下覆盖一个，所以儿子结点只需要覆盖自身就行了。dp[u][4] += dp[son][3];//向下覆盖到孙子，所以儿子只需要保证向下覆盖一个就行，往下递推。}if (vec[u].empty()) {dp[u][1] = dp[u][2] = 1;//当没有儿子的时候只能选择自身作为消防站。}else {//否则：dp[u][1] = dp[u][2] = inf;//为了在min使用的时候方便for (int i = 0; i < vec[u].size(); i++) {int son = vec[u][i];int f1 = dp[son][0];//向上覆盖一个结点，意味着至少一个儿子节点需要向上覆盖两个结点。int f2 = dp[son][1];//只覆盖自己，意味着至少一个儿子结点需要向上覆盖一个结点。for (int j = 0; j < vec[u].size(); j++) {//其他儿子没必要向上继续覆盖了，只需要一个就行。if (i == j)continue;//儿子重合就继续遍历别的儿子。int son_o = vec[u][j];//遍历其他儿子。f1 += dp[son_o][3];//由于选中了一个儿子向上覆盖了，其他儿子的状态无所谓，因为取最小值，所以状态最好是向下覆盖的f2 += dp[son_o][2];//同理}dp[u][1] = min(dp[u][1], f1);//选择当前数量与我们孩子选择之后的数量的最小值。dp[u][2] = min(dp[u][2], f2);}}for (int i = 1; i <= 4; i++) {dp[u][i] = min(dp[u][i], dp[u][i - 1]);//如果一个结点可以向上覆盖两个点，那么它就一定包含向上覆盖一个点的状态，所以需要从中选取最优状态，一直推下去。}
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n;for (int i = 2; i < n + 1; i++) {int x;cin >> x;vec[x].push_back(i);//没有双向构图，是因为这里的结点是相对确定的，小编号一定是在最上面的。}dfs(1);cout << dp[1][2] << endl;//最后我们选择覆盖自身的结点，因为我们覆盖之后都是最佳状态了，当然是保证本层能够覆盖完，并且当前结点就是根结点，没法向上覆盖。return 0;
}这篇关于洛谷 P2279 [HNOI2003] 消防局的设立的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
