RPG的錯(cuò)排

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 22778    Accepted Submission(s): 9117

Problem Description

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

Input

輸入的數(shù)據(jù)里有多個(gè)case,每個(gè)case包括一個(gè)n，代表有幾個(gè)女生，（n<=25）, n = 0輸入結(jié)束。

Sample Input

1
2
0

Sample Output

1
1

解題思路：

公式：dp[ n ] = ( n-1 ) * ( dp[n-1] + dp[n-2] )

解析公式：比如有n個(gè)元素，各對(duì)應(yīng)n個(gè)正確位置，dp[n]表示這n個(gè)元素全部排錯(cuò)的可能。

比如有元素：1 2 3 4 5 ... k ... n

1.假設(shè)第n個(gè)元素，要它在錯(cuò)誤的位置上，則有n-1種情況。

2.對(duì)于剩下的n-1個(gè)元素，隨便取一個(gè)位置上的元素k，要它在錯(cuò)誤的位置上，則有2種情況

1）它在第n個(gè)元素的位置，相當(dāng)于n和k兩個(gè)元素交換位置，和其它沒有關(guān)系，剩余n-2個(gè)元素愛怎么排就怎么排，dp[n-2]

2）不在第n個(gè)元素的位置，假設(shè)把n作為k的正確位置，則1 2 3 4 5...(k)...n，除去正確位置k，就是n-1個(gè)元素放在n-1個(gè)位置上，dp[n-1]。

初始化：

dp[1]=0;

dp[2]=1;

dp[ n ] = ( n-1 ) * ( dp[n-1] + dp[n-2] );

代碼：

#include<stdio.h>
long long ans[20]={1,0,1,2};
long long c[30][30];///C(n,m) = C(n-1,m) + C(n-1,m-1)
void init()
{
    int i,j;
    for(i=4;i<20;i++)
        ans[i] = (i-1) * ( ans[i-1]+ans[i-2] );
    for(i=0;i<30;i++)
        c[i][0]=1;
    for(i=1;i<30;i++)
        for(j=1;j<=i;j++)
            c[i][j] = c[i-1][j] + c[i-1][j-1];

}
int main()
{
    init();
    int i,n;
    while(scanf("%d",&n) && n)
    {
        long long  res=0;
        for(i=0;i<=n/2;i++)
            res += ans[i] * c[n][i];
        printf("%lld\n",res);
    }
    return 0;
}