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/
标签:语句,...,缩进,Python,样例,statement From: https://www.cnblogs.com/onlyblues/p/17744398.html