ZOJ 2625 Rearrange Them（DP）

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1625

题目大意：将n个数重新排列，使得每个数的前一个数都不能和之前的一样，求一共有多少种排列方法

ample Input:

3
4

Sample Output:

3
11

分析：

　　CrazyAC's 解题报告：
　　本题一道ＤＰ题　仔细想想不难的
　　首先我们确定状态F[N]表示所产生的新排列的情况数
　　那么F[N]=f(F[N-1]) 怎么来确定他呢？
　　由于F[N-1]是排好了；所以只要把N往里插，唯一不可插的地方就是N-1后；所以共有N-1情况，
　　那么F[N]=(N-1)*F[N-1] (1)似乎这个式子就对了　但是自己手写几组数据是不对的　郁闷中啊～～～
　　但仔细想想肯定是漏情况了　在哪呢？原来是在我们已经排除的那些组合里，举个例子：N=3
　　是有3种排列:1 3 2;2 1 3;3 2 1
　　那么N=4 时，如果只考虑1 3 2;2 1 3;3 2 1这3种就少情况了，原因出在2 3 1；3 1 2这两
　　个排列没考虑；只要在2 3 1中的2 3之间插4，在3 1 2中的1 2之间插4即可；由此可以发现
　　在(1)中要加一个参数g(N-1)其表示在N-1个数的排列中，有唯一一对原顺序的排列情况
　　g(N)如何确定？我们只要用捆绑一对数的思想就可以；举个例子：把1 2 3 4 5 6中的2 3看　
　　成一个数其等价与1 2 3 4 5，所以g(N)=h(F[N-1]),由于捆绑对数就是N-1,就是(1 2 ,2 3, 3 4...)
　　那么g(N)就确定了：g(N)=(N-1)*F[N-1]；所以完成状态方程：F[N]=(N-1)*F[N-1]+(N-2)*F[N-2];
　　注意边界条件F[0]=0 F[1]=0 F[2]=1 F[3]=3（要用大数）

代码如下：

#include <stdio.h>
#include <string.h>

int f[101][202];

void add(int a,int b,int c){
    int i,car=0,k;
    for(i=0;i<=200;i++){
        k=b*f[b][i]+c*f[c][i]+car;
        f[a][i]=k%10;
        car=k/10;
    }
}

void DP(){
    int i;
    memset(f,0,sizeof(f));
    f[0][0]=0;
    f[1][0]=0;
    f[2][0]=1;
    f[3][0]=3;
    for(i=4;i<=100;i++){
        add(i,i-1,i-2);
    }    
}

int main()
{
    int i,j,n;
    DP();
    while(scanf("%d",&n)!=EOF){
        if(n==0 || n==1){
            printf("0
");
            continue;
        }
        for(i=200;i>=0;i--)
            if(f[n][i]) break;
        for(j=i;j>=0;j--)
            printf("%d",f[n][j]);
        printf("
");
    }
    return 0;
}