题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5151
题解：
有n个椅子，编号为1到n。
现在有n个同学，编号为1到n，从第一个同学开始选择要坐的位子，并且这个同学不能坐同时满足下面三个条件的椅子。
1、左右都有相邻的位子
2、左右相邻的位子都是空的。
3、左右两边的位子颜色不同。
问总共有多少种坐法。
题解：
dp[i][j]表示坐满编号为i到j的椅子的类数。
现在第一个开始坐的人选择的是第t个位子，则dp[i][j]+=dp[i][t-1]*dp[t+1][j]*C[j-i][t-i]，其中组合数C表示安排t-i个人在左边的组合数。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 const int mod = 1e9 + 7; 9 const int maxn = 111; 10 11 int n; 12 int arr[maxn]; 13 LL dp[maxn][maxn],C[maxn][maxn]; 14 15 void pre() { 16 C[0][0] = 1; 17 for (int i = 1; i < maxn; i++) { 18 C[i][0] = 1; 19 for (int j = 1; j <= i; j++) { 20 C[i][j] = (C[i-1][j - 1] + C[i - 1][j]) % mod; 21 } 22 } 23 } 24 25 LL dfs(int i, int j) { 26 if (i == j) return dp[i][j] = 1; 27 if (i > j) return 0; 28 if (dp[i][j] != -1) return dp[i][j]; 29 LL &ret = dp[i][j] = 0; 30 ret=(ret+dfs(i + 1, j)+dfs(i, j - 1))%mod; 31 for (int mid = i + 1; mid <= j - 1; mid++) { 32 if (arr[mid - 1] ^ arr[mid + 1]) continue; 33 ret =(ret+dfs(i, mid - 1)*dfs(mid + 1, j)%mod*C[j - i][mid - i])%mod; 34 } 35 return ret; 36 } 37 38 void init() { 39 memset(dp, -1, sizeof(dp)); 40 } 41 42 int main() { 43 pre(); 44 while (scanf("%d", &n) == 1 && n) { 45 init(); 46 for (int i = 1; i <= n; i++) scanf("%d", arr + i); 47 LL ans=dfs(1, n); 48 printf("%lld\n", ans); 49 } 50 return 0; 51 }