树型DP # 战略游戏

原题链接

---

题目解读

f[u][0] 表示 u点上不放士兵的最小花费

f[u][1] 表示 u点上放士兵的最小花费

如果u点不放士兵，那么其子节点必须放士兵，不然这两条边不能同时被瞭望

如果u点放士兵，那么其子节点可放可不放，取min计算即可

完整代码

//这里是引入了一些常用的头文件,和一些常规操作
//第一行是因为该死的编译器不让直接用scanf
#define _CRT_SECURE_NO_WARNINGS 1
#define _USE_MATH_DEFINES //启用M_PI的定义
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define MAX 0x3f3f3f3f
#define MIN -0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 1510;
int e[N], ne[N], h[N],idx;
int n, f[N][2];
bool st[N];

void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa) {
f[u][0] = 0;
f[u][1] = 1;

for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa)continue;
dfs(j, u);
f[u][0] += f[j][1];
f[u][1] += min(f[j][0],f[j][1]);
}
}

int main() {
memset(h, -1, sizeof h);

cin >> n;
for (int i = 1; i <= n; i++) {
int id, cnt;
cin >> id >> cnt;
while (cnt--) {
int ver;
cin >> ver;
add(id, ver);
st[ver] = true;
}
}

int root = 0;
while (st[root])root++;

dfs(root,-1);

cout << min(f[root][0], f[root][1]);

return 0;
}

参考

本篇文章参考于 ACWING算法平台
董晓算法
感谢🌹

---

🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻

🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹

😇 本篇文章可能存在多处不足，如有修改意见，可以私信或者评论我哦 😇

---

原文地址：https://blog.csdn.net/mzh1213/article/details/144803199

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！