NC20265 [SCOI2008]着色方案(记忆化搜索)

题目链接

题意：





题解：

AC代码

/*
    Author : zzugzx
    Lang : C++
    Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 1e6 + 10;
//const int N = 1e3 + 10;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

ll dp[16][16][16][16][16][6], t[6];
ll dfs(int a, int b, int c, int d, int e, int la) {
    if (dp[a][b][c][d][e][la] != -1)
        return dp[a][b][c][d][e][la];
    if (a + b + c + d + e == 0)
        return 1;
    ll ans = 0;
    if (a) ans = (ans + (a - (la == 2)) * dfs(a - 1, b, c, d, e, 1)) % mod;
    if (b) ans = (ans + (b - (la == 3)) * dfs(a + 1, b - 1, c, d, e, 2)) % mod;
    if (c) ans = (ans + (c - (la == 4)) * dfs(a, b + 1, c - 1, d, e, 3)) % mod;
    if (d) ans = (ans + (d - (la == 5)) * dfs(a, b, c + 1, d - 1, e, 4)) % mod;
    if (e) ans = (ans + e * dfs(a, b, c, d + 1, e - 1, 5)) % mod;
    return dp[a][b][c][d][e][la] = ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++){
        int x;
        cin >> x;
        t[x]++;
    }
    memset(dp, -1, sizeof dp);
    cout << dfs(t[1], t[2], t[3], t[4], t[5], 0);
    return 0;
}