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

2016-03-14 15:06:39来源:[db:出处]作者:[db:作者]人点击

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 vertically2. The vertexes of the bricks should be placed on integer lattice points3. 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 011 1 1 201 1 1 211 2 1 2111 2 0 2011 2 0 2112 2 0 010102 2 0 001102 2 0 011114 5 3 511111110111010111111

样例输出:

001112102954

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

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

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

代码:

#include #include #include #include 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<

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

微信扫一扫

第七城市微信公众平台