动态规划 杂题 ·

151017模拟

题目
此处内容需要 才可见

今天考的题比较简单,一个半小时AK了。但是后来机房突然停电.....幸好代码早早就交了= =

T1 表达式

感觉好久没做这种类型的题了,题目给的信息非常准确严谨。首先空格不能直接吃掉,而是应该当作一个正常字符来处理。然后就可以把所有连续的数所在区间设为合法区间,最后DP一下即可。

T2 食物链

更水,题目就是让求从入度为0的点到出度为0的点的路径数,直接DFS+记忆化即可。

T3 棋盘路径

同“上学路线”,唯一的区别是这个模数给的非常良心,不用CRT再搞一遍了。

设f[i]:从起点到第i个障碍,不经过前i-1个障碍的方案数,有如下方程:

$$f_{i}=C_{x_{i}+y_{i}}^{x_{i}}-\sum_{j,x_{j}<=x_{i},y_{j}<=y_{i}}f_{j}*C_{x_{i}-x_{j}+y_{i}-y_{j}}^{x_{i}-x_{j}} $$

把终点当作最后一个障碍,直接DP就好了。

 

参与评论