HDOJ 1465 不容易系列之一

题目地址:

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)

代码:

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 // Author: Tanky Woo
// HDOJ 1465
 
#include <iostream>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1465 不容易系列之一》有34个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注