【每日一题】7月20日题目精讲—着色方案

来源：牛客网：
@[toc]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

有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<=k<=15 ,1<= ci <=5

题解：

记忆化搜索
dp[a][b][c][d][e][last]
表示每一种颜色分别剩下啊a,b,c,d,e个方案数，有a种一个（可以涂1块木块的有多少种颜***种两个，c种三个....e种五个，last表示上一次用的是可以涂last个木块的油漆
因为我们不能连续涂两块相同的颜色，如果上一次用的还能涂i次的油漆，那么当前就多一种还能涂i-1次的油漆未使用
所以如果b-1的话，a要+1，一次类推都是这样
然后考虑转移方程：

dp[a][b][c][d][e][1]=dp[a-1][b][c][d][e][1]*a+dp[a+1][b-1][c][d][e][2]*b+dp[a][b+1][c-1][d][e][3]*c+dp[a][b][c+1][d-1][e][4]*d+dp[a][b][c][d+1][e-1][5]*e

我们在递推中可以写成这种形式

if(a1) ans = (ans + 1ll * (a1 - (last == 2)) * dfs(a1 - 1, a2, a3, a4, a5, 1)) % mod;

（last==2）则是特判上一种颜色的种类，否则会造成重复

代码：

#include <bits/stdc++.h>

const int mod = 1e9 + 7;
using namespace std;

typedef long long ll;

inline ll read() {
  ll f = 1, x = 0;
  char c = getchar();
  while(c < '0' || c > '9') {
    if(c == '-')    f = -1;
    c = getchar();
  }
  while(c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  return f * x;
}

void print(ll x) {
  if(x < 10) {
    putchar(x + 48);
    return ;
  }
  print(x / 10);
  putchar(x % 10 + 48);
}



ll dp[20][20][20][20][20][10];
int n, a[10];

ll dfs(int a1, int a2, int a3, int a4, int a5, int last) {
  if(dp[a1][a2][a3][a4][a5][last]) return dp[a1][a2][a3][a4][a5][last];
  ll ans = 0;
  if(a1) ans = (ans + 1ll * (a1 - (last == 2)) * dfs(a1 - 1, a2, a3, a4, a5, 1)) % mod;
  if(a2) ans = (ans + 1ll * (a2 - (last == 3)) * dfs(a1 + 1, a2 - 1, a3, a4, a5, 2)) % mod;
  if(a3) ans = (ans + 1ll * (a3 - (last == 4)) * dfs(a1, a2 + 1, a3 - 1, a4, a5, 3)) % mod;
  if(a4) ans = (ans + 1ll * (a4 - (last == 5)) * dfs(a1, a2, a3 + 1, a4 - 1, a5, 4)) % mod;
  if(a5) ans = (ans + 1ll * a5 * dfs(a1, a2, a3, a4 + 1, a5 - 1, 5)) % mod;
  return dp[a1][a2][a3][a4][a5][last] = ans;
}

int main() {
  n = read();
  for(int i = 1; i <= n; i++) {
    int x = read();
    a[x]++;
  }
  for(int i = 1; i <= 5; i++) dp[0][0][0][0][0][i] = 1;
  print(dfs(a[1], a[2], a[3], a[4], a[5], 0));
    return 0;
}