刷油漆

刷油漆

描述

有 n 辆车排成一排，还有m 种不同颜色的油漆，其中第i 种油漆够涂ai 辆车，同时所有油漆恰好能涂完n 辆车。若任意两辆相邻的车颜色不能相同，有多少种涂油漆的方案？

输入

第一行包含一个正整数m。

接下来一行包含m 个正整数，第 i 个正整数表示ai。

输

输出一个整数，表示答案除以 23333 的余数。

样例 1 输入

样例 1 输

样例 1 解释

10 个方案分别是：

131323

132313

231313

312313

313123

313132

313213

313231

321313

323131

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

n 为 ai 之和。

对于 50%的数据，n ≤ 10；

对于 100%的数据，m ≤ 20，ai ≤ 5。时间：10 sec

空间：512 MB

提示

[注意到 ai≤5，所以我们可以将“还能涂 1 辆车的油漆种类数”、“还能涂 2 辆车的油漆种类

数”、...、“还能涂 5 辆车的油漆种类数”设计成状态，思考一下便能得到转移。]

代码

#include <iostream> #include <vector> #include<string.h>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */ const int N = 21, mo = 23333;

//f:记忆已经计算过的答案，减少重复的计算int f[N][N][N][N][N][6];

//动态规划(记忆化搜索)，求当车数目为a+b+c+d+e时涂油漆的方案数

//a:够涂1辆车的油漆种类数

//b:够涂2辆车的油漆种类数

//c:够涂3辆车的油漆种类数

//d:够涂4辆车的油漆种类数

//f:够涂5辆车的油漆种类数

//last:若last==2则表示前一辆车图的油漆是从b中取出来的,last==3则表示是从c中取出来的，以此类推

//返回值:方案数

int dp(int a, int b, int c, int d, int e, int last)

{

if ((a | b | c | d | e) == 0)//n==0,返回1，即空也表示1种方案

return 1;

if (f[a][b][c][d][e][last] != -1)//如果之前计算过答案，直接返回

return f[a][b][c][d][e][last];

long long ret = 0;

//以下(last==2)等表达式的意思是:若这个表达式成立得到的是1，否则是0

//假设有a>0，则最开始从属于a的油漆中选择一个，给第一辆车上色，然后减去这一个油漆并递归(最开始时last!=2，故乘a说明了有a中油漆种类数这么多种可能)

if (a)

ret += dp(a - 1, b, c, d, e, 1)*(a - (last == 2));//若last==2,则表示上一辆车是从b里取出来的放到了a里(即某一种油漆原先够涂2辆车，后来给前一辆车上色后只够涂1辆车了)， 所以a中可以选择的油漆种类数要少一个

if (b)

ret += dp(a + 1, b - 1, c, d, e, 2)*(b - (last == 3));//同理,b少一个，则a会加一个

if (c)

ret += dp(a, b + 1, c - 1, d, e, 3)*(c - (last == 4));//同理

if (d)

ret += dp(a, b, c + 1, d - 1, e, 4)*(d - (last == 5));//同理

if (e)

ret += dp(a, b, c, d + 1, e - 1, 5)*e;//同理

f[a][b][c][d][e][last] = ret % mo;

return ret % mo;

}

//b:b[i]表示有多少种油漆够涂i辆车int b[6];

// n辆车，m种油漆，第i种油漆够涂ai辆车，同时所有油漆恰好能涂完n辆车。若任意两辆相邻的车颜色不能相同，有多少种涂油漆的方案

// m：如题

// a：长度为m的数组，意义如题

// 返回值：方案数

int getAnswer(int m, vector<int> a) {

/* 请在这里设计你的算法 */

memset(f, -1, sizeof f);//一开始f初始化为-1，表示没有计算过

for (int i = 0; i < m; ++i)//计算b数组

b[a[i]]++;

return dp(b[1], b[2], b[3], b[4], b[5], 0) % mo;

}

// ================= 代码实现结束 =================

int main() {

int m;

scanf("%d", &m);

vector<int> a;

for (int i = 0; i < m; ++i) {

int x;

scanf("%d", &x);

a.push_back(x);

}

printf("%d\n", getAnswer(m, a));

return 0;

}