题目大意:个沙茶,被编号1至n排完队之后.每个沙茶希望自己的相邻的两人只要无一个人的编号和自己的编号相差为(+1或-1就行).现在想知道,存在多少方案满足沙茶们如此不苛刻的条件.
计数dp
状态:表示推到第i个数字,有j对数字是相差1的且i与i-1相邻/不相邻
分析
考虑与的关系
将插入到两者中间,拆散了一对但是多了一对,依然还是对,故方案来自于
将插入到的另一侧,多了一对.现在有对,故当时状态只有对,因此方案来自于
为了满足相邻的条件,我们可以必须在的旁边插入,又因为两边都可以满足要求,所以方案数目要加倍.故方案为
分析
依旧是考虑与的关系
我们将插入到任何一对里面都会破坏一对,因为当前是对,所以当时的状态就必须是对,因此方案来自于,又因为有个位置可以选(别忘记我们不能拆开那对,)因此方案总数为
类比上一个情况,我们可以初步得到方程,又因为有个位置可以选,所以总方案数为
也有可能是不去拆开那些相邻的关系
可以插入到平凡的世界:
- :这种情况会出现个,因为当前共有个位置可以插入,但是考虑到插入于中间后,不会产生新的贡献,故,因此总方案数:
- :类比上一个,只不过稍微简单一些:故总方案数:
综上所述
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的理解
我们由谁推过来,一定是由推过来那个状态所演变的,假如我现在只有个,但是推过来那个有个,意味着我这次的转移的意义是少一个