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

题目链接

题意：
$有n个木块$
$k种油漆，每种c_i个$
$c_1+c_2+……+c_k=n$
$相邻两个木块不能涂相同颜色$
$求方案数$
题解：
$k<=15,c_i<=5$
$数据很小，所以可以直接考虑暴力算法$
$但是枚举每种颜色的话，颜色种类数是15，仍然会超时$

$但是c_i很小，可以从这里进行操作$
$可以每次选择固定的c_i进行使用$
$记忆化搜索5种个数的颜色$
$dp[a][b][c][d][e][la]$
$表示现在有a种1个，b种2个，e种5个颜色的油漆，并且上一个用了la个颜色的$
$对于每次使用，会使得当前个数颜色的油漆减少$
$使得当前个数减一的颜色油漆增加$
$所以如果上次使用的油漆颜色是这次使用颜色个数加一$
$就需要减去一个，就是上次使用的颜色，使其不会相邻$
$然后直接搜索并且维护值即可$

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;
}

本文地址：https://blog.csdn.net/qq_43756519/article/details/107405543