题目
3 刷墙(wall.c/cpp/pas)
3.1 题目描述
Will 被指派去刷墙. 他⼀共需要刷N ⾯墙, 每⾯墙要求刷⼀种颜⾊. 他⼀共有N 桶油漆, 这些油漆⼀共有3
种颜⾊, 每种颜⾊的油漆分别有C0, C1, C2 桶. 刷⼀⾯墙需要⽤⼀桶油漆, 这N 桶油漆恰好可以刷完这N ⾯墙
(C0 + C1 + C2 = N).
但刷墙也不是随便可以刷的. Will 要求, 相邻的墙⾯的颜⾊⼀定要满⾜他的要求. 他有时会希望某两种颜⾊可
以不连续出现. 他想知道, 在满⾜他的要求下, ⼀共由多少种刷墙的⽅式呢?
3.2 输入格式(wall.in)
第⼀⾏四个整数C0;C1;C2;K, 分别代表每种颜⾊的油漆桶数, 以及Will 的要求数.
接下来K ⾏每⾏两个整数Xi; Yi, 代表颜⾊为Xi 和Yi 的油漆不能相邻(例如, 0 和1 不能相邻, 则出现相邻墙
⾯是0,1 或者是1,0 都是不合法的).
3.3 输出格式(wall.out)
⼀⾏⼀个整数, 总的刷墙⽅式对109 + 7 = 1000000007 取模后的值.
3.4 样例输入
1 2 2 3
0 0
1 1
2 2
3.5 样例输出
12
3.6 样例解释
共有1 + 2 + 2 = 5 ⾯墙, 颜⾊0 有⼀桶油漆, 颜⾊1 有两桶油漆, 颜⾊2 有两桶油漆; Will 要求相同颜⾊的不
能相邻.
3.7 数据规模及约束
对于30% 的数据, 满⾜Ci 5;
对于50% 的数据, 满⾜Ci 30;
对于100% 的数据, 满⾜0 Ci 100; 0 K 6; 0 Xi; Yi 2.
3.8 时间空间限制
1s, 256M
3
分析
写出一个30分的爆搜不是什么难事，
- dfs(x, y, z, p) 现在剩余C0x 桶, C1y 桶, C2z 桶, 最后刷的颜色是p
- 然后枚举下一面墙刷什么颜色
- 从dfs(C0; C1; C2) 开始刷, 一直刷到dfs(0,0,0) 结束
这样我们就很容易想到接下来100分算法的状态怎么写了，
- 设F[x][y][z][p] 是现在剩余C0x 桶, C1y 桶, C2z 桶, 最后刷的颜色是p, 一共有多少种方案
- 然后进行一波顺推，推到答案F[0][0][0][p]，答案是F[0][0][0][0]...F[0][0][0][2]的最大值
程序
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXC = 100 + 1, MOD = 1000000007; 4 int ban1, ban2, f[MAXC][MAXC][MAXC][3], c1, c2, c3, ans, m; 5 bool ban[3][3]; 6 int main() 7 { 8 freopen("wall.in","r",stdin); 9 freopen("wall.out","w",stdout); 10 cin >> c1 >> c2 >> c3 >> m; 11 for (int i = 1; i <= m; i++) 12 cin >> ban1 >> ban2, ban[ban1][ban2] = ban[ban2][ban1] = true; 13 if(c1) 14 f[1][0][0][0] = 1; 15 if(c2) 16 f[0][1][0][1] = 1; 17 if(c3) 18 f[0][0][1][2] = 1; 19 for (int i = 0; i <= c1; i++) 20 for (int j = 0; j <= c2; j++) 21 for (int k = 0; k <= c3; k++) 22 { 23 if (i) 24 { 25 int g = f[i][j][k][0]; 26 if(i<c1 && !ban[0][0]) 27 (f[i+1][j][k][0] += g) %= MOD; 28 if(j<c2 && !ban[0][1]) 29 (f[i][j+1][k][1] += g) %= MOD; 30 if(k<c3 && !ban[0][2]) 31 (f[i][j][k+1][2] += g) %= MOD; 32 } 33 if (j) 34 { 35 int g = f[i][j][k][1]; 36 if(i<c1 && !ban[1][0]) 37 (f[i+1][j][k][0] += g) %= MOD; 38 if(j<c2 && !ban[1][1]) 39 (f[i][j+1][k][1] += g) %= MOD; 40 if(k<c3 && !ban[1][2]) 41 (f[i][j][k+1][2] += g) %= MOD; 42 } 43 if (k) 44 { 45 int g = f[i][j][k][2]; 46 if(i<c1 && !ban[2][0]) 47 (f[i+1][j][k][0] += g) %= MOD; 48 if(j<c2 && !ban[2][1]) 49 (f[i][j+1][k][1] += g) %= MOD; 50 if(k<c3 && !ban[2][2]) 51 (f[i][j][k+1][2] += g) %= MOD; 52 } 53 } 54 int ans = ((f[c1][c2][c3][0] + f[c1][c2][c3][1]) % MOD + f[c1][c2][c3][2]) % MOD; 55 cout << ans << endl; 56 return 0; 57 }