首页 > 代码库 > codevs 1697 ⑨要写信
codevs 1697 ⑨要写信
传送门
1697 ⑨要写信
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
琪露诺(冰之妖精)有操控冷气的能力。能瞬间冻结小东西,比普通的妖精更危险。一直在释放冷气的她周围总是非常寒冷。
由于以下三点原因……
- 琪露诺的符卡 冰符“Icicle Fall”-Easy的弹幕有够蠢的,只要站在她的正前方就没任何弹幕会碰到你;
- ZUN在《红魔乡》中介绍她时已经说她有点笨笨的了;
- 在ZUN放出《东方花映冢》的介绍图时,在图中把琪露诺放在了⑨的位置上,并以“⑨笨蛋”简单带过,从此“⑨”及“笨蛋”就成为她的别名了……
所以琪露诺便得到了“笨蛋”的别称。
某日,琪露诺又2了……
她写了N封信要装到N个信封里面,却全都装错了……现在想知道有多少种装错的可能性。
输入描述 Input Description
信和信封的数量N。
输出描述 Output Description
装错的可能性的数量。
样例输入 Sample Input
输入样例1
2
|
输入样例2
4
|
样例输出 Sample Output
输出样例1
1
|
输出样例2
9
|
数据范围及提示 Data Size & Hint
1≤N≤100
【题目大意】n封信错排。
【思路】错排问题。递推公式。
f[n]表示n封信错排的可能数。
证明:现在要对第n封信进行错排,有n-1个位置可以选择。假设选择位置k。
对位置k原有的信进行错排,有两种情况。
(1)到位置n,那么n,k已经错排好了,再加上剩下n-2封信的错排,f[n-2]。
(2)k没有放到位置n,+f[n-1].
分步乘法计数原理和分类加法计数原理
f[n]=(n-1)*(f[n-2]+f[n-1]);
【code】
#include<iostream> #include<cstdio> using namespace std; int n,f[120]; long long dp(int n) { if(n==1)return 0; if(n==2)return 1; else return (n-1)*(dp(n-1)+dp(n-2)); } int main() { scanf("%d",&n); printf("%lld\n",dp(n)); return 0; }
没写高精会T。 ToT~~
codevs 1697 ⑨要写信
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。