首页 > ACM题库 > HDU-杭电 > HDU 4804-Campus Design-动态规划-[解题报告]HOJ
2015
09-18

HDU 4804-Campus Design-动态规划-[解题报告]HOJ

Campus Design

问题描述 :

Nanjing University of Science and Technology is celebrating its 60th anniversary. In order to make room for student activities, to make the university a more pleasant place for learning, and to beautify the campus, the college administrator decided to start construction on an open space.
The designers measured the open space and come to a conclusion that the open space is a rectangle with a length of n meters and a width of m meters. Then they split the open space into n x m squares. To make it more beautiful, the designer decides to cover the open space with 1 x 1 bricks and 1 x 2 bricks, according to the following rules:

1. All the bricks can be placed horizontally or vertically
2. The vertexes of the bricks should be placed on integer lattice points
3. The number of 1 x 1 bricks shouldn’t be less than C or more than D. The number of 1 x 2 bricks is unlimited.
4. Some squares have a flowerbed on it, so it should not be covered by any brick. (We use 0 to represent a square with flowerbet and 1 to represent other squares)

Now the designers want to know how many ways are there to cover the open space, meeting the above requirements.

输入:

There are several test cases, please process till EOF.
Each test case starts with a line containing four integers N(1 <= N <= 100), M(1 <= M <= 10), C, D(1 <= C <= D <= 20). Then following N lines, each being a string with the length of M. The string consists of ‘0’ and ‘1’ only, where ‘0’ means the square should not be covered by any brick, and ‘1’ otherwise.

输出:

There are several test cases, please process till EOF.
Each test case starts with a line containing four integers N(1 <= N <= 100), M(1 <= M <= 10), C, D(1 <= C <= D <= 20). Then following N lines, each being a string with the length of M. The string consists of ‘0’ and ‘1’ only, where ‘0’ means the square should not be covered by any brick, and ‘1’ otherwise.

样例输入:

1 1 0 0
1
1 1 1 2
0
1 1 1 2
1
1 2 1 2
11
1 2 0 2
01
1 2 0 2
11
2 2 0 0
10
10
2 2 0 0
01
10
2 2 0 0
11
11
4 5 3 5
11111
11011
10101
11111

样例输出:

0
0
1
1
1
2
1
0
2
954

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

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

思路:插头DP的变形,只要多考虑1X1的情况即可,然后DP多开一维表示使用1X1的个数

代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;

const int MOD = 1000000007;
int n, m, c, d, pre = 0, now = 1;
long long dp[2][25][1222];
char g[105][15];

int main() {
	while (~scanf("%d%d%d%d", &n, &m, &c, &d)) {
		int maxs = (1<<m);
		memset(dp[now], 0, sizeof(dp[now]));
		dp[now][0][maxs - 1] = 1;
		for (int i = 0; i < n; i++)
			scanf("%s", g[i]);
  		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				swap(pre, now);
				memset(dp[now], 0, sizeof(dp[now]));
				int tmp = g[i][j] - '0';
				if (tmp) {
					for (int k = 0; k <= d; k++) {
						for (int s = 0; s < maxs; s++) {
							if (k && (s&1<<j))
								dp[now][k][s] = (dp[now][k][s] + dp[pre][k - 1][s]) % MOD;//放1X1
							if (j && !(s&1<<(j-1)) && (s&1<<j))
								dp[now][k][s|1<<(j-1)] = (dp[now][k][s|1<<(j-1)] + dp[pre][k][s]) % MOD;//横放1X2
  							dp[now][k][s^1<<j] = (dp[now][k][s^1<<j] + dp[pre][k][s]) % MOD;//竖放1X2
						}
    				}
    			}
    			else {
    				for (int k = 0; k <= d; k++) {
    					for (int s = 0; s < maxs; s++) {
    						if ((s&1<<j))
								dp[now][k][s] = (dp[now][k][s] + dp[pre][k][s]) % MOD;//不能放的情况,和放1X1类似
         				}
        			}
       			}
   			}
  		}
  		long long ans = 0;
  		for (int i = c; i <= d; i++)
  			ans = (ans + dp[now][i][maxs - 1]) % MOD;
  		printf("%lld\n", ans);
 	}
	return 0;
}

参考:http://blog.csdn.net/accelerator_/article/details/26097779