[Codeforces] 909C. Python Indentation

題目連結:http://codeforces.com/problemset/problem/909/C

---

我不會DP QAQ
本題狀態可以訂成$dp[i][j]$代表到第$i$個statement時有$j$個intent的方法數，那轉移想了想後就可以得到，如果前面是for statement，那顯然現在的東西就只能擺在跟他同一個intent，而若前一個是普通的statement，則我們可以擺到intent比較小的任意一個位置。而這樣的話複雜度會變成$O(N^3)$，但是其實我們可以透過預處理前綴和以達到$O(N^2)$的複雜度。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MOD = 1000000007;
const int N = 5000 + 5;

bool arr[N];
lld dp[N][N], sum[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		string ss; cin>>ss;
		if(ss[0]=='s') arr[i] = 1;
		else arr[i] = 0;
	}
	auto psum = [](int l, int r){
		// 0-base [l, r]
		if(l) return sum[r]-sum[l-1];
		else return sum[r];
	};
	dp[0][0] = 1;
	for(int i=1;i<=n;i++){
		if(arr[i-1]){
			sum[0] = dp[i-1][0];
			for(int j=1;j<=n;j++) sum[j] = (sum[j-1]+dp[i-1][j])%MOD;
			if(arr[i]) for(int j=0;j<=n;j++) dp[i][j] = (psum(j, n)+MOD)%MOD;
			else for(int j=1;j<=n;j++) dp[i][j] = (psum(j-1, n)+MOD)%MOD;
		}else{
			if(arr[i]) for(int j=0;j<=n;j++) dp[i][j] = dp[i-1][j];
			else for(int j=1;j<=n;j++) dp[i][j] = dp[i-1][j-1];
		}
	}
	lld ans = 0;
	for(int j=0;j<=n;j++) ans = (ans+dp[n][j])%MOD;
	cout << ans << '\n';
	return 0;
}