Codeforces 909C - Python Indentation

Author Avatar
Jimmy Zhang Jan 07, 2018
  • Read this article on other devices

题面

Python 中语句块并没有大括号包围,而是靠缩进来定义的。

现在有一种简化版的 Python,只含有两种语句:

  • s:Simple statement,即一般的语句。
  • f:For statement,即循环语句(相当于 for),并且其循环体不可为空。

现在给你一段没有缩进的这种简化版 Python 的代码,请你计算有多少种合法的 Python 程序。

题目链接

动态规划!

我们来看看第 nn 行语句。不管第 nn 行语句是哪类语句,其可能的缩进实际上完全取决于第 n1n - 1 行:

  • 若第 n1n - 1 行是 f ,第 nn 行的缩进只可能比第 n1n - 1 行多 1;
  • 若第 n1n - 1 行是 s ,第 nn 行的缩进可以是 0 ~ 第 n1n - 1 行缩进中的任意一值(即小于等于 n1n - 1 行的缩进)。

基于此发现,我们可以用 dp[i][j]dp[i][j] 表示状态,表示第 ii 行缩进为 jj 时的方案个数。边界条件即 dp[0][0]=1dp[0][0] = 1

同时,我们也不难推出状态转移方程:

  • 若第 i1i - 1 行为 f,那么第 ii 行缩进为 jj 的情况种数实际上等于第 i1i - 1 行缩进为 j1j - 1 的情况种数:
    dp[i][j]=dp[i1][j1]dp[i][j] = dp[i - 1][j - 1]

  • 若第 i1i - 1 行为 s,那么第 ii 行的缩进一定是小于等于i1i - 1 行的缩进。反过来看,也就是说第 ii 行缩进为 jj 的情况种数是第 i1i - 1 行缩进为 jj , j+1j + 1 … 一直到最大可能的缩进值的所有方案数之和(由于只有 f 语句可能带来缩进,所以最大缩进值就是之前语句中 f 的个数,下面公式中记作 MM )。
    dp[i][j]=k=jMdp[i1][k]dp[i][j] = \sum\limits_{k = j}^{M} dp[i - 1][k]

那么最后我们所要求的总合法方案数就是(同样记最大可能缩进为 MM):

k=0Mdp[i][k]\sum\limits_{k = 0}^{M} dp[i][k]

具体实现?

朴素实现

Submission #33981342

算法复杂度达到了 O(n3)\mathcal{O}(n^3),不 TLE 才怪……

树状数组维护前缀和

可以参考一下 Leohh 大佬的博文: 链接

倒着循环维护后缀和

Submission #33983065

刚才的朴素算法主要是在处理第二种情况(第 i1i - 1 行为 s )时复杂度高了,其原因则是因为求和的过程中做了很多重复运算。我们发现:
dp[i][0]=dp[i1][0]+dp[i1][1]+...+dp[i1][M]dp[i][1]=dp[i1][1]+dp[i1][2]+...+dp[i1][M]...dp[i][M]=dp[i1][M]\begin{aligned}
& dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + … + dp[i - 1][M] \
& dp[i][1] = dp[i - 1][1] + dp[i - 1][2] + … + dp[i - 1][M] \
& … \
& dp[i][M] = dp[i - 1][M]
\end{aligned}

因此我们没有必要在计算每一个 dp[i][j]dp[i][j] 时都把 k=jMdp[i1][k]\sum\limits_{k = j}^{M} dp[i - 1][k] 算一遍,只需要维护一个后缀和就可以了。

int suffixSum = 0;
for (int j = maxIndentation; j >= 0; j--)
{
    suffixSum += dp[i - 1][j];
    suffixSum %= mod;
    dp[i][j] = suffixSum;
}

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/01/07/codeforces-909c/