题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2625
Time Limit: 2 Seconds Memory Limit: 65536 KB

Problem Description:

N people stand in a line, and we numbered them 1,2...n, and now you are asked to rearrange them. The ith people is considred in the front of the (i+1)th, after the rearrange, everyone the people in front of whom can not be the same one as before. How many different strategies you can do the rearrange.

Input:

Each test case just contains one integer, the number of people you have to rearrange.

Output:

The number of strategies you have to rearrange them, with the condition above.

Sample Input:

3
4

Sample Output:

3
11

Problem solving report:

Description: 给一个数n，重新排列1-n之间的数，要求 i 和 i + 1(i < n)不能是顺序的，比如n=3时，排列有123、132、213、231、312、321，其中123、231、312是不符合要求的。
Problem solving: 令f[i]表示长度为i的符合序列个数。则对于已知的f[0]~f[i-1]，我们来推f[i]。因为f[i-1]表示长度i-1符合序列个数。则加入新的元素i,那么i处除i-1后面外，其余全部可以放，共i-1个位置。除了这种从符合条件推符合条件外，还可以从不符合条件推：前一组中有且仅有一对数(k,k+1)相连，则新加入的i插入两个数当中也能变为符合条件的序列。这样的序列有几个呢：我们考虑相连的方式，长度i-1***i-2种((1,2),(2,3)...(i-2,i-1))。又对于相连(k,k+1)，它前面不能是k-1，后面不能是k+2，所以可以将相连数看做一个序列元素来解。则这种情况的种数为(i-2)*f[i-2]。最后得出递推式：f[i]=(i-1)*f[i-1]+(i-2)*f[i-2]。题目没有给出范围，一开始直接写的错了，后来才用大整数写的。

#include <stdio.h>
#include <string.h>
int f[110][210];
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] = 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)) {
        if (n < 2) {
            printf("0\n");
            continue;
        }
        for (i = 200; i >= 0 && !f[n][i]; i--);
        for (j = i; j >= 0; j--)
            printf("%d", f[n][j]);
        printf("\n");
    }
    return 0;
}