HDOJ 1465 不容易系列之一

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

1、当有N封信的时候，前面N-1封信可以有N-1或者 N-2封错装

 

2、前者，对于每一种错装，可以从N-1封信中任意取一封和第 N封错装，故=F(N-1) * (N-1)

 

3、后者简单，只能是没装错的那封信和第N封信交换信封，没装错的那封信可以是前面N-1封信中的任意一个，故= F(N-2) * (N-1)

 

基本形式：f[1]=0;   f[2]=1
递归式：f[n]= (n-1)*( f[n-1] + f[n-2])   排错公式

 (以上分析来自刘春燕老师的课件，)

 

 

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
    int n;
    long long a[21];
    a[1] = 0;
    a[2] = 1;
    a[3] = 2;
    for(int i=4;i<21;i++)
    {
        a[i] = (i-1)*(a[i-2] + a[i-1]);
    }
    while(cin>>n)
        cout<<a[n]<<endl;
    return 0;

}