当前位置： 移动技术网 > 移动技术>移动开发>IOS > NC20265 [SCOI2008]着色方案(记忆化搜索)

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

2020年07月23日  | 移动技术网移动技术  | 我要评论

题目链接

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

但是ci很小，可以从这里进行操作但是c_i很小，可以从这里进行操作
可以每次选择固定的ci进行使用可以每次选择固定的c_i进行使用
记忆化搜索5种个数的颜色记忆化搜索5种个数的颜色
dp[a][b][c][d][e][la]dp[a][b][c][d][e][la]
表示现在有a种1个，b种2个，e种5个颜色的油漆，并且上一个用了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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网