本文共 1817 字，大约阅读时间需要 6 分钟。

题目链接:

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 
   
    #include 
    
     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;}
    
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/86998222 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！