Blog·Tanky WooABOUTRSS

HDOJ 1465 不容易系列之一

23 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=1465

思路:

传说中的“错排公式”=。=

当有n封信时,前n-1封或前n-2封可能错。

如果前n-1封错,则可以把第n封与前面任意n-1封交换而使n封全错。有f(n-1)*(n-1)

如果前n-2封错,则可以把对的那封与第n封交换,而对的那封可以是n-1封内任意一封。所以有f(n-2)*(n-1)

所以 f(n) = (f(n-1)+f(n-2)) * (n-1)

代码:

 

 // Author: Tanky Woo
// HDOJ 1465

#include 
using namespace std;

__int64 f[22];
int main()
{

    f[1] = 0;
    f[2] = 1;
    f[3] = 2;
    for(int i = 4; i <= 20; ++i)
        f[i] = (i-1)*(f[i-2]+f[i-1]);
    int num;
    while(scanf("%d", &num;) != EOF)
//是说用__int64没效果,原来输出时忘了加%I64d
        printf("%I64d\n", f[num]);   
    return 0;
}