Python缩进
在 Python 中，代码块没有显式的开始/结束或大括号来标记代码块的开始和结束。
相反，代码块是通过缩进定义的。
我们考虑一个极其简化的 Python 子集，其只有两种类型的语句：简单语句和 $For$ 语句。
- 简单语句（ Simple statements ）仅占一行，每行一个。
- $For$ 语句（ For statements ）是复合语句：它们包含一个或多个其它语句。$For$ 语句由循环头和循环体共同组成。循环头是一个以 $for$ 开头的单独行。循环体是比循环头缩进一级的语句块。循环体可以包含两种类型的语句。循环体不能为空。
给定 $n$ 个没有缩进的语句，请你计算，通过合理缩进，一共可以形成多少个不同的有效 Python 代码。
输入格式
第一行包含整数 $n$。
接下来 $n$ 行，每行包含一个字符 f（表示 $For$ 语句）或 s（表示简单语句），用来描述一行给定语句的类型。
保证最后一行一定是简单语句。
输出格式
一个整数，表示可以形成的不同有效 Python 代码的数量对 $10^9+7$ 取模后的结果。
数据范围
前 $3$ 个测试点满足 $1 \le n \le 5$。
所有测试点满足 $1 \le n \le 5000$。
输入样例1：
4 s f f s
输出样例1：
1
样例1解释
可以形成一种有效代码：
simple statement for statement for statement simple statement
输入样例2：
4 f s f s
输出样例2：
2
样例2解释
可以形成以下两种有效代码：
for statement simple statement for statement simple statement
或
for statement simple statement for statement simple statement
解题思路
先来条喜讯，最后保研去了 985 的 CS，结果还是比较满意的了，唯一遗憾的地方就是没做 TCS 的方向。所以之后的时间就会相对轻松许多，不过之前因为忙着推免的事导致半个多月没碰过算法，现在算是又回坑了吧。虽然半个月没碰了，但感觉退步了好多，比如这道题我都不会做（）。之后的计划还是每天会抽些时间写算法题和博客，同时优化一下博客的编写规范，并尝试写一些 AtCoder 和牛客上面的题解等。
这题关键的地方是上一条语句能决定当前语句能缩进的的级别。比如当前有如下的程序：
1 s ... 2 for ... 3 s ... 4 for ... 5 s ...
可以发现上一条语句是 $s$ 语句，那么无论当前是 $s$ 语句还是 $f$ 语句，都可以缩进到不超过上一条语句级别的任意级别：
1 s ... 2 f ... 3 s ... 4 f ... 5 s ... 6 s/f ...
1 s ... 2 f ... 3 s ... 4 f ... 5 s ... 6 s/f ...
1 s ... 2 f ... 3 s ... 4 f ... 5 s ... 6 s/f ...
而如果上一条语句是 $f$ 语句，那么无论当前是 $s$ 语句还是 $f$ 语句，都只能缩进到上一条 $f$ 语句的下一个级别。比如：
1 s ... 2 f ... 3 s ... 4 f ... 5 f ... 6 s/f ...
因此定义状态 $f(i,j)$ 表示由前 $i$ 条语句构成，且第 $i$ 条语句缩进了 $j$ 级的所有方案的数量。根据第 $i-1$ 条是 $f$ 语句还是 $s$ 语句来进行状态划分。
如果第 $i-1$ 条语句是 $f$ 语句，那么第 $i$ 条语句只能缩进到上一条语句的下一个级别（由于第 $i$ 条语句是第 $j$ 级，因此上一条语句就是第 $j-1$ 级），因此状态转移方程是 $f(i,j) = f(i-1,j-1)$。
如果第 $i-1$ 条语句是 $s$ 语句，那么可以缩进到不超过第 $i-1$ 条语句级别的任意级别。由于第 $i$ 条语句的级别是 $j$，因此第 $i-1$ 条语句的级别要大于等于 $j$，即可以是 $j, \, j+1, \, \ldots , \, i-1$。因此状态转移方程就是 $f(i,j) = \sum\limits_{k=j}^{i-1}{f(i-1,k)}$。很明显需要对这个状态转移方程进行优化，可以发现由于 $f(i,j+1) = \sum\limits_{k=j+1}^{i-1}{f(i-1,k)}$，因此有 $f(i,j) = f(i-1,j) + f(i,j+1)$。实现的时候只需倒着枚举 $j$，这样要计算 $f(i,j)$ 时，$f(i,j+1)$ 已经算出来了。
那么最终的答案就是 $\sum\limits_{i=1}^{n}{f(n,i)}$。
AC 代码如下，时间复杂度为 $O(n^2)$：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 5010, mod = 1e9 + 7; 5 6 char s[N]; 7 int f[N][N]; 8 9 int main() { 10 int n; 11 scanf("%d", &n); 12 for (int i = 1; i <= n; i++) { 13 scanf("%s", s + i); 14 } 15 f[1][1] = 1; 16 for (int i = 2; i <= n; i++) { 17 for (int j = i; j; j--) { 18 if (s[i - 1] == 'f') f[i][j] = f[i - 1][j - 1]; 19 else f[i][j] = (f[i - 1][j] + f[i][j + 1]) % mod; 20 } 21 } 22 int ret = 0; 23 for (int i = 1; i <= n; i++) { 24 ret = (ret + f[n][i]) % mod; 25 } 26 printf("%d", ret); 27 28 return 0; 29 }
参考资料
AcWing 5268. Python缩进（AcWing杯 - 周赛）：https://www.acwing.com/problem/content/5271/