HDU 5151 Sit sit sit 区间dp

题目链接：

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个人在左边的组合数。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int mod = 1e9 + 7;
const int maxn = 111;

int n;
int arr[maxn];
LL dp[maxn][maxn],C[maxn][maxn];

void pre() {
    C[0][0] = 1;
    for (int i = 1; i < maxn; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j - 1] + C[i - 1][j]) % mod;
        }
    }
}

LL dfs(int i, int j) {
    if (i == j) return dp[i][j] = 1;
    if (i > j) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    LL &ret = dp[i][j] = 0;
    ret=(ret+dfs(i + 1, j)+dfs(i, j - 1))%mod;
    for (int mid = i + 1; mid <= j - 1; mid++) {
        if (arr[mid - 1] ^ arr[mid + 1]) continue;
        ret =(ret+dfs(i, mid - 1)*dfs(mid + 1, j)%mod*C[j - i][mid - i])%mod;
    }
    return ret;
}

void init() {
    memset(dp, -1, sizeof(dp));
}

int main() {
    pre();
    while (scanf("%d", &n) == 1 && n) {
        init();
        for (int i = 1; i <= n; i++) scanf("%d", arr + i);
        LL ans=dfs(1, n);
        printf("%lld
", ans);
    }
    return 0;
}