CF909C Python Indentation 题解

sunqihuan · 2025-10-26 10:06:40 · 题解

动规题目。设 f_{i,j} 表示第 i 个语句缩进 j 次，如果前一个语句为循环那么这一语句一定在这个循环下面，缩进 j 次的方案数自然就是前一个语句缩进 j-1 次。否则，如果这个语句缩进 j 次，那么上一个语句一定缩进 j 次以上，维护一下后缀和即可。

显然空间爆炸，所以需要滚动数组。

代码：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 5e3 + 5, mod = 1e9 + 7;

int n, dp[N], p, res, dp2[N];
char s[N];

signed main()
{
    cin >> n;
    dp2[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        char c;
        cin >> c;
        s[i] = c;
    }
    for (int i = 1; i <= n; i ++ )
    {
        if (s[i - 1] != 'f')
        {
            for (int j = p; j >= 0; j -- ) dp[j] = (dp[j] + dp[j + 1] + dp2[j]) % mod;
        }
        else
        {
            for (int j = ++ p; j >= 1; j -- ) dp[j] = dp2[j - 1];
        }
        for (int j = 0; j <= p; j ++ ) dp2[j] = dp[j], dp[j] = 0;
    }
    for (int i = 0; i <= p; i ++ ) res = (res + dp2[i]) % mod;
    cout << res << endl;
    return 0;
}