HDU Sit sit sit (区间DP+组合数)

题目大意：有 n 张椅子，n 个人，所有人都可以按照任意顺序坐在任意一张椅子上，但是同时满足这三种情况的椅子不能坐：
1.椅子上有左右两张相邻的椅子。
2.左右相邻的椅子不是空的。
3.左右相邻的椅子颜色不同。
如果当前学生没有椅子可以坐，他就会离开。

问一共有几种坐法？

思路：区间dp+组合数

dp[i][j] : 记录在 i ~ j 之间满足题目要求的排列数。

C[i][j] : （组合数）在 i 个人中挑选 j 个人。

在长度为 1 的时候，排列数肯定为 1，在长度为 2的时候排列数肯定为 2，当长度大于等于 3 的时候就要开始分裂类讨论了。第一种情况最有一个人坐在两边的情况，第二种情况最后一个人不坐在两边的情况。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
const int N=1e2+5;
const int mod=1e9+7;
int a[N],dp[N][N],C[N][N];
signed main(){
	for(int i=0;i<=101;i++){//杨辉三角求组合数 
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++){
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
		}
	}
	int n;
	while(cin >> n){
		for(int i=1;i<=n;i++){
			cin >> a[i];
			dp[i][i]=1;//长度为 1 ，有一种排列方式 
			if(i+1<=n) dp[i][i+1]=2; // 长度为 2，有两种排列方式 
		}
		for(int len=2;len<n;len++){
			for(int i=1;i<=n;i++){
				int j=i+len;
				if(j>n) break;
				dp[i][j]=(dp[i+1][j]+dp[i][j-1])%mod;//最后一个人坐在两边的情况 
				for(int k=i+1;k<j;k++){
					if(a[k-1]==a[k+1]) dp[i][j]=(dp[i][j]+dp[i][k-1]*dp[k+1][j]%mod*C[j-i][k-i]%mod)%mod;//最后一个人坐在第 k 个位置且满足题目要求的情况 
					//j-i就是当前长度 len（ k 除外），k-i就是在 k 之前的位置的个数，C[j-i][k-i]就是在(j-i)个人里挑(k-i)个人坐到 k 前面的那几个位子去 
				}
			}
		}
		cout << dp[1][n] << endl;
	}
	return 0;
}