[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...