首页 > 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


  1. 对于未知总是会恐惧,最难迈出的是第一步。若要 出去走走会看到不一样的世界,注意安全。有的人喜欢安逸害怕离别,有的人习惯行走不想停留。 不一样的生活,各有各的喜怒哀乐。

  2. 对于未知总是会恐惧,最难迈出的是第一步。若要 出去走走会看到不一样的世界,注意安全。有的人喜欢安逸害怕离别,有的人习惯行走不想停留。 不一样的生活,各有各的喜怒哀乐。

  3. 对于未知总是会恐惧,最难迈出的是第一步。若要 出去走走会看到不一样的世界,注意安全。有的人喜欢安逸害怕离别,有的人习惯行走不想停留。 不一样的生活,各有各的喜怒哀乐。

  4. 对于未知总是会恐惧,最难迈出的是第一步。若要 出去走走会看到不一样的世界,注意安全。有的人喜欢安逸害怕离别,有的人习惯行走不想停留。 不一样的生活,各有各的喜怒哀乐。

  5. 对于未知总是会恐惧,最难迈出的是第一步。若要 出去走走会看到不一样的世界,注意安全。有的人喜欢安逸害怕离别,有的人习惯行走不想停留。 不一样的生活,各有各的喜怒哀乐。

  6. 对于未知总是会恐惧,最难迈出的是第一步。若要 出去走走会看到不一样的世界,注意安全。有的人喜欢安逸害怕离别,有的人习惯行走不想停留。 不一样的生活,各有各的喜怒哀乐。

  7. 对于未知总是会恐惧,最难迈出的是第一步。若要 出去走走会看到不一样的世界,注意安全。有的人喜欢安逸害怕离别,有的人习惯行走不想停留。 不一样的生活,各有各的喜怒哀乐。

  8. 对于未知总是会恐惧,最难迈出的是第一步。若要 出去走走会看到不一样的世界,注意安全。有的人喜欢安逸害怕离别,有的人习惯行走不想停留。 不一样的生活,各有各的喜怒哀乐。

  9. 对于未知总是会恐惧,最难迈出的是第一步。若要 出去走走会看到不一样的世界,注意安全。有的人喜欢安逸害怕离别,有的人习惯行走不想停留。 不一样的生活,各有各的喜怒哀乐。

  10. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  11. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  12. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  13. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  14. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  15. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  16. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  17. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  18. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  19. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  20. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  21. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  22. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  23. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  24. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  25. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的

  26. 你那是野队效率吧,加上联队的领土的一起算就没这么多了。我野队效率也比盒子高50。也就是说我打联队基本是掉效率,涨胜率的