洛谷P3914 - 染色计数

 题解 / 洛谷
被浏览

CSP-S 前要多做树上问题(主要是因为去年 NOIP D1T3、D2T1、D2T3 全是树上问题,然后爆炸了)

这题一看就是树形DP,状态也是一眼就能想到的。

令 $f_{i,j}$ 表示 $i$ 这个点染成 $j$ 的方案数,枚举 $son_i$ 的颜色来转移。

最后答案即为 $\sum_{i=1}^{m}f_{1,i}$ 。

CF498B Name That Tune

被浏览

作为一道英文题先解释一下题意。

用 $T$ 秒时间按顺序听 $N$ 首歌,第 $i$ 首歌播放时间为 $t_i$ 秒,且每播放一秒都会有 $p_i$ 的概率被识别出来,跳到下一首。某首歌播放时间过完默认被识别,也跳到下一首。若时间有剩余而歌已全部听完则直接结束。求识别出歌数量的期望。

看见题目就想到期望DP。

第一眼想到的方程是设 $f_{i,j}$ 表示第 $i$ 秒识别到第 $j$ 首歌的期望,不难想出一个 $O(n^3)$ 的算法。

枚举一个 $k$ 表示第 $j$ 首歌已经放了几秒,注意一下边界即可。

洛谷P1107 - 雷涛的小猫

 题解 / 洛谷
被浏览

我们根据题意,发现这是一个 DP 题,定义$f_{i,j}$表示在高度为$i$,当前要爬的树为$j$所能获得的最大柿子数。

易得状态转移方程:$f_{i,j}=max(f_{i-1,j},f_{i-delta,k}) (1\leq k \leq n)$ 当$i>delta$时后一项成立。

于是我们得到了一个时间复杂度为$O(H \times N^2)$,空间复杂度为$O(N \times H)$的算法啦。。