NC20265 [SCOI2008]着色方案(记忆化搜索)
程序员文章站
2022-04-12 09:13:25
题目链接题意:有n个木块有n个木块有n个木块k种油漆,每种ci个k种油漆,每种c_i个k种油漆,每种ci个c1+c2+……+ck=nc_1+c_2+……+c_k=nc1+c2+……+ck=n相邻两个木块不能涂相同颜色相邻两个木块不能涂相同颜色相邻两个木块不能涂相同颜色求方案数求方案数求方案数题解:k<=15,ci<=5k<=15,c_i<=5k<=15,ci<=5数据很小,所以可以直接考虑暴力算法数据很小,所以可以直接考虑暴力算法数据很小,所以...
题意:
题解:
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
上一篇: composer拓展包开发