跟上面那篇轮廓线dp是一样的，但是多了两个条件，一个是在原图上可能有些点是不能放的（即障碍），所以转移的时候要多一个判断color[i][j]是不是等于1什么的，另外一个是我们可以有多的1*1的骨牌，1*1的骨牌使用数量一定要在[c,d]之间，所以状态加多一维，转移的时候多一种情况（放1的）。那么怎么初始化呢？有两种方法，一种是dp[0][0][d]=1,最后的答案的因为一定要用[c,d]之间，所以答案是dp[(t+1)&1][0][0~d-c].另外一种是dp[0][0][c~d]=1,最后答案是dp[(t+1)&1][0][0]
学了就觉得很简单，60行不到的代码让我们和银奖失之交臂，痛心疾首呀~
下面放一发代码~
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<vector>#include<cmath>#include<cstdio>#define mod 1000000007#define maxn 100#define maxm 10using
namespace std;char
color[maxn + 50][maxm + 5];int
dp[2][1 << (maxm+1)][25];int
n, m, c, d;int
main(){ while
(~scanf("%d%d%d%d", &n, &m, &c, &d)) { for
(int i = 0; i < n; i++) scanf("%s", color[i]); memset(dp, 0, sizeof(dp)); dp[0][0][d] = 1; int
t = 0; for
(int i = 0; i < n; i++){ for
(int j = 0; j < m; j++){ t = i*m + j; memset(dp[(t + 1) & 1], 0, sizeof(dp[(t + 1) & 1])); for
(int k = 0; k < 1 << m; k++){ for
(int r = 0; r <= d; r++){ if
((k >> j) & 1 || color[i][j] == ‘0‘){ dp[(t + 1) & 1][k&~(1 << j)][r] = (dp[t & 1][k][r] + dp[(t + 1) & 1][k&~(1 << j)][r]) % mod; } else{ if
(j + 1 < m && color[i][j + 1] == ‘1‘&& !(k >> (j + 1) & 1)){ dp[(t + 1) & 1][k | (1 << (j + 1))][r] = (dp[t & 1][k][r] + dp[(t + 1) & 1][k | (1 << (j + 1))][r]) % mod; } if
(i + 1 < n&&color[i + 1][j] == ‘1‘){ dp[(t + 1) & 1][k | (1 << j)][r] = (dp[t & 1][k][r] + dp[(t + 1) & 1][k | (1 << j)][r]) % mod; } if
(r > 0){ dp[(t + 1) & 1][k][r - 1] = (dp[t & 1][k][r] + dp[(t + 1) & 1][k][r - 1]) % mod; } } } } } } int
ans = 0; for
(int i = d - c; i >= 0; i--){ ans = (ans + dp[(t + 1) & 1][0][i]) % mod; } printf("%d\n", ans); } return
0;} |
原文：http://www.cnblogs.com/chanme/p/3561326.html