[luoguP2016] 战略游戏（DP）

传送门

f[i][0]表示不选当前节点，当前节点的所有儿子节点都选
f[i][1]表示选当前节点，儿子节点可选可不选

#include <cstdio> #include <cstring> #include <iostream> #define N 1501 #define min(x, y) ((x) < (y) ? (x) : (y)) int n, cnt; int head[N], to[N << 1], next[N << 1], f[N][2]; bool vis[N]; //f[i][0]表示不选当前节点，当前节点的所有儿子节点都选 //f[i][1]表示选当前节点，儿子节点可选可不选 inline int read() inline void add(int x, int y) inline void dfs(int u) } } int main() } dfs(1); printf("%d\n", min(f[1][0], f[1][1])); return 0; }

　　

上一篇：[luoguP2401] 不等数列

下一篇：[luoguP1773] 符文之语_NOI导刊2010提高（02）（DP）

---

DP