CF909C Python Indentation 题解

动规题目。设

f_{i,j}

表示第

i

个语句缩进

j

次，如果前一个语句为循环那么这一语句一定在这个循环下面，缩进

j

次的方案数自然就是前一个语句缩进

j-1

次。否则，如果这个语句缩进

j

次，那么上一个语句一定缩进

j

次以上，维护一下后缀和即可。

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

代码：

CPP

#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;
}

CF909C Python Indentation 题解

文章操作

相关推荐

评论

CF909C Python Indentation 题解