树的覆盖
\(dp_{i,j,0/1/2}\) 表示以 \(i\) 为根的子树中覆盖 \(j\) 个点的方案数。其中 \(0/1/2\) 分别表示了 \(3\) 种情况。
- \(0\) 表示示当前节点和子节点都没被选中
- \(1\) 表示当前节点被选中,子节点选中与不选中都归于这一类
- \(2\) 表示存在子节点被选中且当前节点不选中
考虑 \(\rm dp\) 转移
枚举已遍历子树中选择几个,再枚举正在遍历的子树中选择几个,根据乘法原理相乘即可。
核心代码:
for (auto v : E[x]) {
if (v == fa) continue;
dfs(v, x);
R(i, 0, sz[x]) {
R(j, 0, sz[v]) {
R(t1, 0, 2) {
R(t2, 0, 2) {
int sum = i + j, p = t1;
if (!t1 && t2 == 1) p = 2, ++sum;
if (t1 == 1 && !t2) ++sum;
tmp[sum][p] += dp[x][i][t1] * dp[v][j][t2];
tmp[sum][p] %= P;
}
}
}
}
sz[x] += sz[v];
R(i, 0, sz[x]) {
R(j, 0, 2) {
dp[x][i][j] = tmp[i][j];
tmp[i][j] = 0;
}
}
}
其中 \(sum\) 表示在已遍历子树与正在遍历的子树的选择下会在 \(x\) 的子树中覆盖几个点。
在这里你会发现一些变化,if (!t1 && t2 == 1) p = 2, ++sum;
!t1
的意思是 \(x\) 不选且它没有儿子选中,然而 t2==1
的意思是 \(x\) 的正在遍历的点要选,所以两个状态矛盾,现在的状态变为了 \(x\) 不选且它有儿子要选,变为状态 \(2\)。两个 ++sum
的意思是有一个点选了而它相邻的点没选,所以覆盖的总数要 \(+1\)。
还有一个细节,代码中用了一个临时数组来存储当前的 \(dp\),否则会用到现在的信息就会发生错误。
几乎完整的代码:
const int N = 2005, P = 1e9 + 7;
int n, sz[N], dp[N][N][3], tmp[N][3];
vector <int> E[N];
void dfs(int x, int fa) {
sz[x] = 1;
dp[x][1][1] = dp[x][0][0] = 1;
for (auto v : E[x]) {
if (v == fa) continue;
dfs(v, x);
R(i, 0, sz[x]) {
R(j, 0, sz[v]) {
R(t1, 0, 2) {
R(t2, 0, 2) {
int sum = i + j, p = t1;
if (!t1 && t2 == 1) p = 2, ++sum;
if (t1 == 1 && !t2) ++sum;
tmp[sum][p] += dp[x][i][t1] * dp[v][j][t2];
tmp[sum][p] %= P;
}
}
}
}
sz[x] += sz[v];
R(i, 0, sz[x]) {
R(j, 0, 2) {
dp[x][i][j] = tmp[i][j];
tmp[i][j] = 0;
}
}
}
}
signed main() {
read(n);
R(i, 1, n - 1) {
int u, v;
read(u, v);
E[u].pb(v), E[v].pb(u);
}
dfs(1, 0);
int ans = 0;
R(i, 0, n) {
ans = dp[1][i][0] + dp[1][i][1] + dp[1][i][2]; ans %= P;
write(ans), ptc('\n');
}
return 0;
}
原文地址:http://www.cnblogs.com/cyyhcyyh/p/16895360.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性