在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

全部文章 / 题解（共3篇）

题解 | #Strategic game#

本题翻译过来：在一棵书上每条边都必须有一个或多个士兵节点，求最少的士兵节点的个数。那么对于每一个节点来说有选与不选两种情况：dp[i][0/1]; 如果选的话儿子节点选与不选都行：dp[i][1] = 1 + (儿子节点累加和)min(dp[u][0], dp[u][1]); 如果不选的话儿子...

C++ 树状dp

2023-10-20

1 271

题解 | #没有上司的舞会#

题目中的意思翻译过来其实是在一颗数上相邻的节点只能选择一个，那么最大的和为多少。那么对于每一个节点来说就有选与不选两种状态：dp[i][0/1] 如果选的话那么以这个节点为根的子树最大和为：dp[i][1] = (f[i]+(所有子树和)dp[u][0]); 如果不选的话那么对于子树来说就有选...

C++ 动态规划树状dp

2023-10-19

1 289

题解 | #小G有一个大树#

对于某个节点来说，如果该节点删除那么就会形成他儿子节点全部独立成一棵树和他父亲节点的那棵树。那么状态转移方程：dp[i] = (total-f[i], (所有儿子节点最大的那个)f[u]) 对于求某个节点下有多少节点来说是一个简答树状dp问题。 f[i] = 1+(所有儿子节点)f[u]; ...

C++ 动态规划树状dp

2023-10-19

1 367