CF1152D
http://codeforces.com/contest/1152/problem/D
大意：給你一個(gè)n,表示一個(gè)長度為2*n的括號(hào)序列则奥，對(duì)于所有合法的序列画恰，建立字典樹理逊，根節(jié)點(diǎn)表示的序列為空序列软棺，讓你找不同頂點(diǎn)的邊有多少個(gè)套媚。
例如 n=2, 答案為 3,圖中藍(lán)色的邊
字典樹
不用關(guān)系每個(gè)節(jié)點(diǎn)表示的確切序列，<<>和<><節(jié)點(diǎn)往下屉来，邊的情況是一樣的蓬抄，因?yàn)槊織l鏈都是一個(gè)合法的序列，他們的長度一樣冤留。
#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碧囊，左括號(hào)比右括號(hào)多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;//左括號(hào)小于右括號(hào)不合法 返回 當(dāng)k=1返回-1纤怒，父節(jié)點(diǎn)試圖連接糯而，但這個(gè)節(jié)點(diǎn)不合法，父節(jié)點(diǎn)方案數(shù)就不會(huì)+1泊窘，抵消了
if(i+j > 2*n) return -k; //括號(hào)合法時(shí)長度超限
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;
}
