Problem Descrption

今年暑假杭電ACM集訓隊第一次組成女生隊,其中有一隊叫RPG,但做為集訓隊成員之一的野駱駝竟然不知道RPG三個人具體是誰誰。RPG給他機會讓他猜猜，第一次猜：R是公主，P是草兒，G是月野兔；第二次猜：R是草兒，P是月野兔，G是公主；第三次猜：R是草兒，P是公主，G是月野兔；......可憐的野駱駝第六次終于把RPG分清楚了。由于RPG的帶動，做ACM的女生越來越多，我們的野駱駝想都知道她們，可現在有N多人，他要猜的次數可就多了，為了不為難野駱駝，女生們只要求他答對一半或以上就算過關，請問有多少組答案能使他順利過關。

Input

輸入的數據里有多個case,每個case包括一個n，代表有幾個女生，（n<=25）, n = 0輸入結束。

Output

1 1

Sample Input

1 2 0

Sample Output

1 1

問題鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2068

問題分析：根據錯列排序的思想

錯排簡單點說就是給n個節點它們原來的位置為i，
然后讓你把它們從新排列使得它們都不在它們原來的位置上。
錯排遞歸公式：f(i) = (i - 1) * (f(i - 1) + f(i - 2)); ?i >= 4 (f(0) = 0, f(1) = 0, f(2) = 1, f(3) = 2);
AC代碼：

#include<iostream> using namespace std; long int c(int n,int m) {long int i,t1=1,t2=1;for(i=n;i>=n-m+1;i--)t1*=i;for(i=1;i<=m;i++)t2*=i;return t1/t2; }int main() {int i,k,r;long int a[15],cr,n;a[0]=0;a[1]=0;a[2]=1;for(k=3;k<=15;k++)a[k]=(k-1)*(a[k-1]+a[k-2]);while(scanf("%I64d",&n)&&n){r=n/2;cr=0;for(i=2;i<=r;i++)cr+=c(n,i)*a[i];//小于n/2的人的錯排的和，即為所求if(n==1||n==2)printf("1\n");else printf("%I64d\n",cr+1);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU2068(错列排序)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。