题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=4804

题意：给定一个图，0是不能放的，然后现在有1X1和1X2方块，最后铺满该图，使得1X1使用次数在C到D之间，1X2次数随便，问有几种放法？

解法：状压DP。dp[i][j][k]代表在第i行，当前状态为j，用了k次1*1的方格的方案数。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
int n,m,c,d;
int dp[102][1025][22];
char maze[110][12];
void dfs(int i, int pos, int now, int step, int j, int k){
	if(k+step > d) return;
	if(maze[i][pos]=='0'){
		if(j&(1<<pos)) dfs(i,pos+1,now|(1<<pos),step,j,k);
		else return;
	}
	else{
		if(pos==m) dp[i][now][k+step]=(dp[i][now][k+step]+dp[i-1][j][k])%mod;
		else{
			if(!((1<<pos)&j)) dfs(i,pos+1,now|(1<<pos),step,j,k);
			else{
				dfs(i,pos+1,now|(1<<pos),step+1,j,k);
				if(pos>0&&(!(now&(1<<(pos-1)))))
					dfs(i,pos+1,now|(1<<(pos-1))|(1<<pos),step,j,k);
				dfs(i,pos+1,now,step,j,k);
			}
		}
	}
}
int main(){
	while(~scanf("%d%d%d%d", &n,&m,&c,&d)){
		int mask = (1<<m)-1;
		memset(dp, 0, sizeof(dp));
		dp[0][mask][0]=1;
		for(int i=1; i<=n; i++){
			scanf("%s", maze[i]);
		}
		for(int i=1; i<=n; i++)
			for(int j=0; j<=mask; j++)
				for(int k=0; k<=d; k++)
					if(dp[i-1][j][k])
						dfs(i,0,0,0,j,k);
		int ans=0;
		for(int i=c; i<=d; i++)
			ans = (ans + dp[n][mask][i])%mod;
		if(ans < 0) ans += mod;
		printf("%d\n", ans);
	}
	return 0;
}