题目背景

四川NOI省选第二试

题目描述

有n个木块排成一行,从左到右依次编号为1~n。你有k种颜色的油漆,其

中第i 种颜色的油漆足够涂ci 个木块。所有油漆刚好足够涂满所有木块,即

c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看,所以你希望统计任意两个相

邻木块颜色不同的着色方案。

输入输出格式

输入格式:

第一行为一个正整数k,第二行包含k个整数c1, c2, ... , ck。

输出格式:

输出一个整数,即方案总数模1,000,000,007的结果。

输入输出样例

输入样例#1:

3
1 2 3

输出样例#1:

10

输入样例#2:

5
2 2 2 2 2

输出样例#2:

39480

输入样例#3:

10
1 1 2 2 3 3 4 4 5 5

输出样例#3:

85937576

说明

50%的数据满足:1 <= k <= 5, 1 <= ci <= 3

100%的数据满足:1 <= k <= 15, 1 <= ci <= 5

题解

暴力记忆化搜索

一开始看到题 我想了个$$dp[i][j][last]$$表示刷到前$$i$$个用了$$j$$种颜色,最后一种颜色为$$last$$的方案数状态

然而似乎并不知道怎么转移诶..

仔细观察题目发现$$c$$的范围非常小,这时候我们就可以有一个大胆的想法:

$$dp[i][j][k][l][m][last]$$表示分别可以刷这么$$i,j,k,l,m$$这么多次的颜色种数,最后一种颜色为$$last$$的方案数

暴力记搜即可

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

const int Maxv = 110; 
const int Mod = 1e9 + 7;  

long long dp[17][17][17][17][17][6]; 
int cnt[6], n, k; 

inline long long DFS(int a, int b, int c, int d, int e, int last) {
    if (dp[a][b][c][d][e][last] != -1) return dp[a][b][c][d][e][last]; 
    if (a + b + c + d + e == 0) return 1; 

    long long res = 0; 
    if (a) res += (a - (last == 2)) * DFS(a - 1, b, c, d, e, 1); 
    if (b) res += (b - (last == 3)) * DFS(a + 1, b - 1, c, d, e, 2); 
    if (c) res += (c - (last == 4)) * DFS(a, b + 1, c - 1, d, e, 3); 
    if (d) res += (d - (last == 5)) * DFS(a, b, c + 1, d - 1, e, 4); 
    if (e) res += e * DFS(a, b, c, d + 1, e - 1, 5); 

    dp[a][b][c][d][e][last] = res % Mod; 
    
    return dp[a][b][c][d][e][last];
}

int main() {
    int n; 
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        int tmp;
        scanf("%d", &tmp); 

        cnt[tmp]++; 
    }

    memset(dp, -1, sizeof(dp)); 
    printf("%lld\n", DFS(cnt[1], cnt[2], cnt[3], cnt[4], cnt[5], 0)); 
    
    return 0; 
}