HDU 5151 Sit sit sit 区间DP + 排列组合

时间：2022-01-23 06:22:45

Sit sit sit

问题描述
在一个XX大学中有NN张椅子排成一排，椅子上都没有人，每张椅子都有颜色，分别为蓝色或者红色。 接下来依次来了NN个学生，标号依次为1,2,3,...,N。 对于每个学生，他会找一张还没有人坐的椅子坐下来。但是如果这张椅子满足以下三个条件他就不会去坐。

1. 这张椅子左右两边都有相邻的椅子

2. 这张椅子左右两边相邻的椅子都不是空的，也就是有人坐下了

3. 这张椅子左右两边相邻的椅子的颜色不同

如果当前的学生找不到椅子坐下，那他就会走掉。

对于当前的某个学生，他可能有很多种椅子的选择来坐。你的任务是计算有多少种不同的全部的学生都坐下来的情况。结果可能很大，输出答案对1000000007({10}^{9}+7)1000000007(10​9​​+7) 取模。
输入说明
输入有多组测试数据。

对于每组测试数据：

第一行为一个整数 N(1\leq N\leq 100)N(1≤N≤100)，第二行为 NN个整数表示椅子的颜色，数的范围为0到1，0代表蓝色，1代表红色。
输出说明
对于每组测试数据，输出答案对1000000007({10}^{9}+7)1000000007(10​9​​+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 ;

}

代码

相关文章