101017模拟 动态规划 杂题

101017模拟

虽然今天考试又翻车了(暴力分都没拿全),但是这套题还是非常值得总结的。 T1 小奇挖矿2 考试的时候注意到+4+7很奇怪,也试着凑了几个数,但是因为写错了没找到规律,乖乖打了暴力(然而处理重复没搞好)。实际上,如果认真把4和7能凑出来的数写出来的话,可以发现,4和7可以凑出{4,7,8,11,12,···
BZOJ3566 [SHOI2014]概率充电器 概率+树形DP 动态规划 期望概率

BZOJ3566 [SHOI2014]概率充电器 概率+树形DP

对现在来说算是非常难的DP,这样计算感觉很不好想啊,但是思路其实很清晰。 首先,这题要求的其实就是每个点被充电的概率,但如果正着推会很复杂,因为充电的情况比较多,所以我们计算每个点不被充电的概率。 假设我们目前在计算点i的值,那么把树划分成三个部分:i的父节点及以上部分,i以及i的子树,i的兄弟节点···
Evensgn剪树枝(tree.*) 树形DP 动态规划 图论

Evensgn剪树枝(tree.*) 树形DP

又是一道树形DP,考试打暴力期望60,然而只骗到了30。思路非常不显然,至今懵逼。设f[i][0]表示i点上方的连通块中不包含黑点,在i的子树中的方案数;f[i][1]相反。这样设计状态,可以考虑砍i点的父边。 设当前考虑的是u点,先不考虑u点的颜色,递归处理u的子树,递归完成后,再考虑f[u]的取···
树形DP:小胖守皇宫 动态规划

树形DP:小胖守皇宫

本题是树形DP,主要的困难在于子节点与父节点的关系上,一共有4种决策,其中子节点选中时,父节点选择与否无影响,所以这两种可以合并。 比较麻烦的情况时父节点和当前节点都没有选中,这样孩子节点必须至少选中一个,因为该点的父节点已经保证由之前的节点所覆盖,而该点的子节点至少有一个被选中,以保证能覆盖到该点···