hdu 2018 母牛的故事 (基础dp,记忆化搜索)

hdu2018题目链接

题意:第1年有1头奶牛,每年生一头奶牛,新生的奶牛从生下来的第四年(包括生下来那年)也开始每年一头奶牛。
问第n年有多少头奶牛。
思路:最容易想到的。。递推一下。。。dp[i] = dp[i-1] + dp[i-3] (注意初始化不是一个dp[1]=1,而是dp[1..4]=1..4)

递推代码:

 

也可以考虑记忆化嘛

理论上应该是所有的dp都可以写成记忆化。。。?

记忆化的好处是不用考虑什么边界的问题。。。坏处是。。可能爆栈。。。。。

 

记忆化代码:

 

codeforces edu1 D. Igor In the Museum

http://codeforces.com/contest/598/problem/D

题意:给第一个地图。 ‘.’是能走的,‘*’是不能走的。每个‘.’和’*’之间有一幅画,给出k个起点,问对于每组起点,最多能观察到多少副画。

思路:dfs.要注意即使只有一个‘*’,从不同方向访问仍然算不同的画。这样就不用标记画是否访问过了。一开始直接暴力dfs..TLE 10

然后发现,如果是在同一个联通快内,能看到的画的最大值是确定的。。如果之前有同一个联通快内的其他点dfs过得到过答案,那么下次就不用再dfs了。。。记得把之前的记过保存下来。。

我具体的写法是把某一次dfs进过的点的恒纵坐标都存起来。。。然后dfs结束后把更新这些沿途中经过的点的答案。。结果还是TLE 10

果然是记忆化写残了。。也不是写残了。。看了几个别人的代码。。。记忆化存的时候是按照某一次来存答案。。而我是按照某个点的坐标。。来存答案。果然还是要提高姿势水平啊。。。SAD