前言

這次模擬賽出的好bt，這道題被出成T1,只有一個人A了，而我卻被卡到了 80 p t s 80pts 80pts，

分析

看一眼題目與資料范圍，搜索時間一定炸，顯然是一道 D p Dp Dp，

設 d p [ i ] [ j ] dp[i][j] dp[i][j]為以 i i i結尾，前面有 j j j個空格的總方案數，

我們可以分為兩種情況：

1.s[i-1]=‘f’

這種情況比較簡單，因為有一個限制是每一個 f f f下面必須不為空，所以說當前這個的位置必須是在上一個字符的下一層，也就是下一個包含在上一個中，

for example:

f
 x
 
x表示'f'或's'

于是我們就可以推出來這樣一個轉移方程：
d p [ i ] [ j ] = d p [ i ? 1 ] [ j ? 1 ] ( s [ i ? 1 ] = = ′ f ′ ) dp[i][j] = dp[i - 1][j - 1](s[i-1]=='f') dp[i][j]=dp[i?1][j?1](s[i?1]==′f′)

2.s[i-1]=‘s’

這種情況稍顯復雜，因為如果上一個字符為 s s s的話，那么下面一個字符就可以在不超過上一個的層數的任何位置，設上一個在第x層，那么這一個位置就可以在x-1,x-2,x-3…2,1這一些層數在0~x-1的位置，故上一個 d p [ i ? 1 ] [ j ] dp[i-1][j] dp[i?1][j]的方案數可以加到 d p [ i ] [ k ] ( 0 < = k < = j ) dp[i][k](0<=k<=j) dp[i][k](0<=k<=j)這里面，

for example:

  s
x

  s
 x
 
  s
  x
  
x表示'f'或's'

于是我們就可以推出來這樣一個轉移方程：
d p [ i ] [ j ] = ∑ ( d p [ i ? 1 ] [ k ] ) dp[i][j] = \sum(dp[i - 1][k]) dp[i][j]=∑(dp[i?1][k])

其中k>=j，

時間復雜度問題

如果第二種世界暴力寫的話，可以發現最壞時間復雜度為 O ( n 3 ) O(n^3) O(n3)，絕對會T，于是考慮后綴和，優化一下時間復雜度，在第二種情況就可以 O ( n ) O(n) O(n)更新，于是總的時間復雜度為 O ( n 2 ) O(n^2) O(n2)，

代碼

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 1000000007
const int MAXN = 5e3 + 5;
int n,sum[MAXN],dp[MAXN][MAXN],ans,Sum[2][MAXN];
char s[MAXN];
int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++) {
		scanf("\n%c",&s[i]);
		if(s[i] == 'f') sum[i + 1] = sum[i] + 1;
		else sum[i + 1] = sum[i];
	}
	if(s[n] == 'f') return printf("0"),0;
	dp[1][0] = 1,Sum[0][0] = 1;
	for(int i = 2;i <= n;i ++) {
		if(s[i - 1] == 's')
		for(int j = sum[i];j >= 0;j --) {
			dp[i][j] += Sum[0][j],dp[i][j] %= MOD;
			Sum[1][j] = Sum[1][j + 1] + dp[i][j],Sum[1][j] %= MOD;
		}	
		else for(int j = sum[i];j >= 0;j --)
		dp[i][j] = dp[i - 1][j - 1],dp[i][j] %= MOD,Sum[1][j] = Sum[1][j + 1] + dp[i][j],Sum[1][j] %= MOD;
		memcpy(Sum[0],Sum[1],sizeof(Sum[1]));
	}
	for(int i = 0;i <= sum[n];i ++)
	ans += dp[n][i],ans %= MOD;
	printf("%d",ans);
	return 0;
}