Question

高分求杭电ACM递推解释

请教杭电ACM 2044 2045 2046 2047 2048 2049 2050几条题的递推式是如何得来的，请高手们详细解释
http://acm.hdu.edu.cn/showproblem.php?pid=2044
http://acm.hdu.edu.cn/showproblem.php?pid=2045
http://acm.hdu.edu.cn/showproblem.php?pid=2046
http://acm.hdu.edu.cn/showproblem.php?pid=2047
http://acm.hdu.edu.cn/showproblem.php?pid=2048
http://acm.hdu.edu.cn/showproblem.php?pid=2049
http://acm.hdu.edu.cn/showproblem.php?pid=2050
特别是2045及2047两题的解释！！！

Answer 1

2045题

数组F[i]保存i个方格有多少种填涂方法。
n个方格可以由n-1个方格和n-2个方格填充得到。
比如，在一涂好的n-1个格子里最后再插入一个格子，就得到了n个格子了。
因为已经填好n-1的格子中，每两个格子的颜色都不相同。
所以只能插入一种颜色。而n-1个格子一共有F[n-1]种填涂方法。所以从n-1格扩充到n格共有F(n-1)种方法。

若前n-1不合法，而添加一个后变成合法，即前n-2个合法，而第n-1个与第1个相同。
这时候有两种填法。
所以
f[n] = f[n-1] + 2 * f[n-2];
f[1] = 3;
f[2] = 6;
f[3] = 6

2047题

我们每次都在原来合法的字符串的最后面再加一个字符，让它仍然是合法的字符串。
这就会出现最后一个字符是O和不是O两种情况，把末尾是O的字符串的个数保存在D[I][0]里，而不是O的保存在D[I][1]里。
在原来的字符串上再加个O，让它依然合法，则原来的字符串末尾必须不为O，即D[n][0] = D[n-1][1]
而在原来的字符串上再加非O，则它对前面字符串的末尾没有要求，而且它还有E、F两种。因此D[n][1] = 2 * (D[n-1][0] + D[n-1][1])
初始D[1][0] = 1; D[1][1] = 2;

2048

N张票的所有排列可能自然是Ann = N!种排列方式
现在的问题就是N张票的错排方式有几种。
首先我们考虑，如果前面N-1个人拿的都不是自己的票，即前N-1个人满足错排，现在又来了一个人，他手里拿的是自己的票。
只要他把自己的票与其他N-1个人中的任意一个交换，就可以满足N个人的错排。这时有N-1种方法。

另外，我们考虑，如果前N-1个人不满足错排，而第N个人把自己的票与其中一个人交换后恰好满足错排。
这种情况发生在原先N-1人中，N-2个人满足错排，有且仅有一个人拿的是自己的票，而第N个人恰好与他做了交换，这时候就满足了错排。
因为前N-1个人中，每个人都有机会拿着自己的票。所以有N-1种交换的可能。

综上所述：f(n) = (i - 1) * [f(n - 1) + f(n - 2)]

我就知道这么多了，希望对你有所帮助。

Answer 2

这么多题目.. 想吓死个人啊

Answer 3

学下动态规划，就会知道这些递推题是多么的基础

Answer 4

我把我的用户名和密码借你用几天吧，你自己去看代码，不懂的地方再问，用户名justeasy 密码：123456