queue2

Posted on Edited on In

题目大意:\(n\)个沙茶,被编号1至n排完队之后.每个沙茶希望自己的相邻的两人只要无一个人的编号和自己的编号相差为\(1\)(+1或-1就行).现在想知道,存在多少方案满足沙茶们如此不苛刻的条件.

计数dp

状态:\(f_{i,j,0/1}\)表示推到第i个数字,有j对数字是相差1的且i与i-1相邻/不相邻

分析\(f_{i,j,1}\)

考虑\(i-1\)与\(i-2\)的关系

  • 若\(i-1\)与\(i-2\)相邻

将\(i\)插入到两者中间,拆散了一对\((i-1,i-2)\)但是多了一对\((i-1,i)\),依然还是\(j\)对,故方案来自于\(f_{i-1,j,1}\)

将\(i\)插入到\(i-1\)的另一侧,多了一对\((i-1,i)\).现在有\(j\)对,故当时状态只有\(j-1\)对,因此方案来自于\(f_{i-1,j-1,1}\)

  • 若\(i-1\)与\(i-2\)不相邻

为了满足\((i-1,i)\)相邻的条件,我们可以必须在\(i-1\)的旁边插入,又因为两边都可以满足要求,所以方案数目要加倍.故方案为\(f_{i-1,j-1,0} \times2\)

分析\(f_{i,j,0}\)

依旧是考虑\(i-1\)与\(i-2\)的关系

  • 若\(i-1\)与\(i-2\)相邻

我们将\(i\)插入到任何一对里面都会破坏一对,因为当前是\(j\)对,所以当时的状态就必须是\(j+1\)对,因此方案来自于\(f_{i-1,j+1,1}\),又因为有\(j+1-1\)个位置可以选(别忘记我们不能拆开\((i-1,i-2)\)那对,)因此方案总数为\(f_{i-1,j+1,1} \times j\)

  • 若\(i-1\)与\(i-2\)不相邻

类比上一个情况,我们可以初步得到方程\(f_{i-1,j+1,0}\),又因为有\(j+1\)个位置可以选,所以总方案数为\(f_{i-1,j,0} \times (j+1)\)

也有可能是\(i\)不去拆开那些相邻的关系

可以插入到平凡的世界:

  • \(f_{i-1,j,1}\):这种情况会出现\((i-j-2+1)\)个,因为当前共有\((i-j-2)\)个位置可以插入,但是考虑到插入于\((i-1,i-2)\)中间后,不会产生新的贡献,故\(+1\),因此总方案数:\(f_{i-1,j,1} \times(i-j-1)\)
  • \(f_{i-1,j,0}\):类比上一个,只不过稍微简单一些:故总方案数:\(f_{i-1,j,0} \times (i-j-2)\)

综上所述

\[f_{i,j,1}=f_{i-1,j,1}+f_{i-1,j-1,1}+f_{i-1,j-1,0}\times 2\]

\[f_{i,j,0}=f_{i-1,j+1,1} \times j+f_{i-1,j+1,0} \times (j+1)\]

\[f_{i,j,0}=f_{i-1,j,1} \times (i-j-1)+f_{i-1,j,0} \times (i-j-2)\]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e3 + 66, mod = 7777777;

int f[N][N][3];

signed main()
{
    int n, i, j;
    n = read();
    f[1][0][0] = 1;
    for (i = 2; i <= n; ++ i)
    {
        for (j = 0; j < i; ++ j)
        {
            f[i][j][1] = (f[i - 1][j][1] + f[i - 1][j - 1][1] + f[i - 1][j - 1][0] * 2) % mod;
            f[i][j][0] = (f[i - 1][j + 1][1] * j + f[i - 1][j + 1][0] * (j + 1)) % mod;
            f[i][j][0] = (f[i][j][0] + f[i - 1][j][1] * (i - 1 - j) + (f[i - 1][j][0] * (i - 2 - j))) % mod;
        }
    }
    put(f[n][0][0]);

    return 0;
}

后记:

第一道学会学透学懂的计数dp,难了我整整两天

神仙状态.

感觉这一道题就加深了我对dp的理解

我们由谁推过来,一定是由推过来那个状态所演变的,假如我现在只有\(j\)个,但是推过来那个有\((j+1)\)个,意味着我这次的转移的意义是少一个\(j\)