Sit sit sit
问题描述
在一个XX大学中有NN张椅子排成一排,椅子上都没有人,每张椅子都有颜色,分别为蓝色或者红色。 接下来依次来了NN个学生,标号依次为1,2,3,...,N。 对于每个学生,他会找一张还没有人坐的椅子坐下来。但是如果这张椅子满足以下三个条件他就不会去坐。
1. 这张椅子左右两边都有相邻的椅子
2. 这张椅子左右两边相邻的椅子都不是空的,也就是有人坐下了
3. 这张椅子左右两边相邻的椅子的颜色不同
如果当前的学生找不到椅子坐下,那他就会走掉。
对于当前的某个学生,他可能有很多种椅子的选择来坐。你的任务是计算有多少种不同的全部的学生都坐下来的情况。结果可能很大,输出答案对1000000007({10}^{9}+7)1000000007(109+7) 取模。
输入说明
输入有多组测试数据。
对于每组测试数据:
第一行为一个整数 N(1\leq N\leq 100)N(1≤N≤100),第二行为 NN个整数表示椅子的颜色,数的范围为0到1,0代表蓝色,1代表红色。
输出说明
对于每组测试数据,输出答案对1000000007({10}^{9}+7)1000000007(109+7)取模。
输入样例
3
1 0 0
4
1 0 0 1
输出样例
4
8
题解: 区间DP+组合计数问题,转移方程为,每次选当前区间最后一个放的位置,然后乘上组合数C[区间长度][左区间长度]
注意dp 数组的初始化 -1
//meek///#include<bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<bitset>
using namespace std ;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
#define fi first
#define se second
#define MP make_pair
typedef long long ll; const int N = ;
const int M = ;
const int inf = 0x3f3f3f3f;
const int MOD = ;
const double eps = 0.000001; int dp[N][N],a[N],n,c[N+][N+];
int dfs(int l,int r) {
if(dp[l][r]!=- ) return dp[l][r];
if(l > r) return ;
int& ret = dp[l][r] = ;
if(l == r) {
if(l == ||r == n||a[l-] == a[r+]) return ret = ;
else return ret = ;
}
for(int i=l;i<=r;i++) {
ret += 1ll*dfs(l,i-)*dfs(i+,r)%MOD*c[r-l][i-l]%MOD;
ret %= MOD;
}
return ret;
}
void init() {
for(int i=;i<=;i++) {
c[i][] = ;
for(int j=;j<=i;j++) {
c[i][j] = (c[i-][j] + c[i-][j-])%MOD;
}
}
}
int main() {
init();
while(scanf("%d",&n)!=-) {
memset(dp,-,sizeof(dp));
for(int i=;i<=n;i++) scanf("%d",&a[i]);
printf("%d\n",dfs(,n));
}
return ;
}
代码