题目描述
https://codeforces.com/problemset/problem/909/C
Solution
我们令 $dp$ 状态为 $f[i][j]$ 表示当前是第 $i$ 个，没有缩进的有 $j$ 行
不妨假设当前的 $for$ 与上个 $for$ 直接有 $k$ 个 $s$
那么我们注意到我们可以将若干个没有缩进的行并入当前 $for$ 中，显然方案数不会重复
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 5010
#define ll long long
using namespace std;
const int p = 1000000007;
int n;
int a[maxn], A[maxn];
int f[maxn][maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
char s[4]; cin >> s + 1;
if (s[1] == 'f') A[i] = 1;
} int cnt = 0;
for (int i = n, w = 0; i; --i)
if (A[i]) a[++cnt] = w, w = 0;
else ++w;
reverse(a + 1, a + cnt + 1); f[cnt + 1][0] = 1;
for (int i = cnt; i; --i) {
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= min(a[i], j); ++k)
f[i][j] = (f[i][j] + f[i + 1][j - k]) % p;
for (int j = n, sum = 0; j; --j) {
sum = (sum + f[i + 1][j]) % p;
f[i][j] = (f[i][j] + sum) % p;
}
}
int ans = 0;
for (int i = 0; i <= n; ++i) ans = (ans + f[1][i]) % p;
cout << ans << "\n";
return 0;
}
|