queue2

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

计数dp

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

分析fi,j,1

考虑i1i2的关系

  • i1i2相邻

i插入到两者中间,拆散了一对(i1,i2)但是多了一对(i1,i),依然还是j对,故方案来自于fi1,j,1

i插入到i1的另一侧,多了一对(i1,i).现在有j对,故当时状态只有j1对,因此方案来自于fi1,j1,1

  • i1i2不相邻

为了满足(i1,i)相邻的条件,我们可以必须在i1的旁边插入,又因为两边都可以满足要求,所以方案数目要加倍.故方案为fi1,j1,0×2

分析fi,j,0

依旧是考虑i1i2的关系

  • i1i2相邻

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

  • i1i2不相邻

类比上一个情况,我们可以初步得到方程fi1,j+1,0,又因为有j+1个位置可以选,所以总方案数为fi1,j,0×(j+1)

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

可以插入到平凡的世界:

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

综上所述

fi,j,1=fi1,j,1+fi1,j1,1+fi1,j1,0×2

fi,j,0=fi1,j+1,1×j+fi1,j+1,0×(j+1)

fi,j,0=fi1,j,1×(ij1)+fi1,j,0×(ij2)

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