跟上面那篇轮廓线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行不到的代码让我们和银奖失之交臂，痛心疾首呀~
下面放一发代码~
#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 10
using 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;
}