CF1152D
http://codeforces.com/contest/1152/problem/D
大意：給你一個n,表示一個長度為2*n的括號序列，對于所有合法的序列，建立字典樹，根節(jié)點(diǎn)表示的序列為空序列，讓你找不同頂點(diǎn)的邊有多少個。
例如 n=2, 答案為 3,圖中藍(lán)色的邊
字典樹
不用關(guān)系每個節(jié)點(diǎn)表示的確切序列，<<>和<><節(jié)點(diǎn)往下，邊的情況是一樣的，因為每條鏈都是一個合法的序列，他們的長度一樣。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3+7;
const int mod = 1e9+7;
int dp[maxn][maxn][2],n; //dp[i][j][k] 表示長度為i，左括號比右括號多j，當(dāng)前點(diǎn)和父節(jié)點(diǎn)有無連線（k）,的方案數(shù)
bool vst[maxn][maxn][2];
int dfs(int i,int j,int k)
{
if(j < 0) return -k;//左括號小于右括號不合法 返回 當(dāng)k=1返回-1，父節(jié)點(diǎn)試圖連接，但這個節(jié)點(diǎn)不合法，父節(jié)點(diǎn)方案數(shù)就不會+1，抵消了
if(i+j > 2*n) return -k; //括號合法時長度超限
if(i == 2*n && j == 0) return 0; //葉子節(jié)點(diǎn)
if(vst[i][j][k]==1) return dp[i][j][k];
vst[i][j][k] = true;
long long tmp = 0;
if(k == 0){ //當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)不連線
tmp = max(dfs(i+1,j-1,1)+dfs(i+1,j+1,0) + 1, //如果沒法跟子節(jié)點(diǎn)連線，+1被抵消
dfs(i+1,j-1,0)+dfs(i+1,j+1,1) + 1);
}else{
tmp = dfs(i+1,j-1,0) + dfs(i+1,j+1,0);
}
return dp[i][j][k] = tmp%mod;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n;
cout<<dfs(0,0,0)<<endl;
return 0;
}
