【DP】 HDOJ 4804 Campus Design

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 105;
const int mod = 1e9+7;

char g[maxn][11];
int dp[2][1 << 10][22];
int n, m, C, D;

void add(int& x, int y)
{
	x += y;
	if(x > mod) x -= mod;
}

void work()
{
	memset(g, '1', sizeof g);
	for(int i = 1; i <= n; i++) scanf("%s", g[i]+1);
	
	memset(dp, 0, sizeof dp);
	int now = 1, pre = 0;
	dp[now][(1 << m) - 1][0] = 1;

	int tt = (1 << m) - 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			now ^= 1;
			pre ^= 1;
			memset(dp[now], 0, sizeof dp[now]);
			for(int k = 0; k < 1 << m; k++) {
				for(int l = 0; l <= D; l++) {
					if(g[i][j] == '0') {
						if(g[i-1][j] == '0') {
							if((k & (1 << m-1)) == 0) add(dp[now][k << 1 & tt][l], dp[pre][k][l]);
						}
						else {
							if((k & (1 << m-1)) != 0) add(dp[now][k << 1 & tt][l], dp[pre][k][l]);
						}
					}
					else {
						if(g[i-1][j] == '0') {
							if((k & (1 << m-1)) == 0) {
								add(dp[now][k << 1 & tt][l], dp[pre][k][l]);
								add(dp[now][(k << 1 | 1) & tt][l+1], dp[pre][k][l]);
								if((k & 1) == 0 && j > 1) add(dp[now][(k << 1 | 3) & tt][l], dp[pre][k][l]);
							}
						}
						else {
							if((k & (1 << m-1)) == 0) {
								add(dp[now][(k << 1 | 1) & tt][l], dp[pre][k][l]);
							}
							else {
								add(dp[now][k << 1 & tt][l], dp[pre][k][l]);
								add(dp[now][(k << 1 | 1) & tt][l+1], dp[pre][k][l]);
								if((k & 1) == 0 && j > 1) add(dp[now][(k << 1 | 3) & tt][l], dp[pre][k][l]);
							}
						}
					}
				}
			}
		}
	}
	
	int st = 0;
	for(int i = 1; i <= m; i++) {
		st <<= 1;
		st |= g[n][i] == '1';
	}
	
	int ans = 0;
	for(int i = C; i <= D; i++) add(ans, dp[now][st][i]);
	printf("%d
", ans);
}

int main()
{
	while(scanf("%d%d%d%d", &n, &m, &C, &D) != EOF) {
		work();
	}
	
	return 0;
}