盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5151 Sit sit sit(区间dp)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5151

题意

有n个人陆续坐到n个椅子上,每张椅子为两种颜色中的一种。每个人每次可以选择一个空位置,如果该空位置两边都有人,且两边的椅子颜色不同,那么他便不能坐下,需要离开。现在问n个人全部坐下的方案数

思路

dp[i][j]表示编号i-j的位置上都有人坐下的方案数。dp[i][i] = 1, dp[i][i+1] = 2
dp[i][j] =sum(dp[i][k-1] dp[k+1][j] C(j-i, k-i-1)) 当i-k-1有人坐下,k+1-j有人坐下,此时来的人坐在k的方案数累积
C(j-i, k-i-1)表示前面的j-i个人有k-i-1个人选择坐在了左边的方案数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int CN = 111;
const int mod = 1000000007;
ll c[CN][CN]= {};
void cinit() {
for(int i = 0; i <= 100; i++) {
c[i][0] = c[i][i] = 1;
for(int j = 1; j < i; j++) {
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
if (c[i][j] > mod) c[i][j] -= mod;
}
}
}
ll dp[CN][CN];
int n, a[CN];
int main () {
cinit();
while(~scanf("%d", &n)) {
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
dp[i][i] = 1;
dp[i][i + 1] = 2;
}
for (int l = 3; l <= n; l++) {
for (int i = 0; i + l <= n; i++) {
int j = i + l - 1;
dp[i][j] = 0;
//head
dp[i][j] += dp[i + 1][j];
//mid
for (int k = i + 1; k <= j - 1; k++) if (a[k - 1] == a[k + 1]) {
dp[i][j] += c[l - 1][k - i] * dp[i][k - 1] % mod * dp[k + 1][j] % mod;
dp[i][j] %= mod;
}
//tail
dp[i][j] += dp[i][j - 1];
dp[i][j] %= mod;
}
}
printf("%I64d\n", dp[0][n - 1]);
}
return 0;
}