Zhuwanxing

分类

dp(2) 剑指offer(3) 题解(7)

/ 注册

全部文章（共12篇）

Strategic game

题目大意对于任意一条边，其都只有两种被覆盖的可能:1.被上面的节点(父节点)覆盖2.被下面的节点(子节点)覆盖故容易推出状态表示和方程dp[i][j]:以i为根的子树的所有边被覆盖且i的状态为j的所有方案的数量最小值(j = 0表示i不放士兵，j = 0为i放士兵)转移方程dp[i][0] = ∑...

比赛题解

2021-04-27

3 540

Cell Phone Network

树的最小支配集问题题目大意：思路:对于任意一个点，只有三种被覆盖的情况1.被自己覆盖2.被自己的子节点覆盖3.被自己的父节点覆盖故很容易推出状态表示dp[i][j]:以i为根的子树的全部节点被覆盖且i节点的覆盖状态为j的所有方案的节点最小值(其中j = 0表示被自己覆盖，j = 1表示被儿子覆盖，...

比赛题解

2021-04-26

1 500