o******3
发帖数: 91 | 1 听了二爷的话，开始做hackerrank
今天被lego blocks绊住了
测试数据集可以过 但是提交数据集就超时了 虽然我用的确实是DP
下面是题目和我的代码，还望指点
You have 4 types of lego blocks, of sizes 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3
and 1 * 1 * 4. Assume you have infinite number of blocks of each type.
You want to make a wall of height N and width M out of these blocks. The
wall should not have any holes in it. The wall you build should be one solid
structure. A solid structure means that it should not be possible to
separate the wall along any vertical line without cutting any lego block
used to build the wall. The blocks can only be placed horizontally. In how
many ways can the wall be built?
Input:
The first line contains the number of test cases T. T test cases follow.
Each case contains two integers N and M.
Output:
Output T lines, one for each test case containing the number of ways to
build the wall. As the numbers can be very large, output the result modulo
1000000007.
Constraints:
1 <= T <= 100
1 <= N,M <= 1000
Sample Input:
4
2 2
3 2
2 3
4 4
Sample Output:
3
7
9
3375
Explanation:
For the first case, the possible walls are:
aa
bc
aa
bb
ab
cc
For the second case, each row of the wall can contain either two blocks of
width 1, or one block of width 2. However, the wall where all rows contain
two blocks of width 1 is not a solid one as it can be divided vertically.
Thus the number of ways is 2 * 2 * 2 - 1 = 7.
PS:”aa” is one lego block of size 1 * 1 * 2, “b” and “c” are lego
blocks of size 1 * 1 * 1.
#include
#include
#include
#include
#include
using namespace std;
int getRes(int width, int height, vector row)
{
vector< vector > res;
vector< vector > total;
res.resize(width+1);
total.resize(width+1);
for(int i=0; i<=width; i++)
{
res[i].resize(height+1);
total[i].resize(height+1);
}
for(int i=0; i
{
res[0][i]=0;
total[0][i]=0;
total[1][i]=1;
res[1][i] = 1;
}
for(int i=0; i
{
res[i][0] = 0;
total[i][0] = 0;
total[i][1]=row[i];
res[i][1] = row[i];
}
for(int h=2; h
for(int w=1; w
total[w][h]=row[w]*total[w][h-1]%1000000007;
for(int w=2; w
{
for(int h=2; h
{
int inValSum = 0;
for(int k=1; k
{
inValSum = inValSum + (total[w-k][h]*res[k][h])%1000000007;
inValSum = inValSum%1000000007;
}
res[w][h]= total[w][h]-inValSum;
if(res[w][h]<0)
res[w][h] = res[w][h]+1000000007;
}
}
return res[width][height]%1000000007;
}
void setRow(vector& row)
{
if(row.size()>0)
row[0]=1;
if(row.size()>1)
row[1]=1;
for(int i=2; i
{
if(i-1>=0)
row[i]=(row[i]+row[i-1])%1000000007;
if(i-2>=0)
row[i]= (row[i]+row[i-2])%1000000007;
if(i-3>=0)
row[i]= (row[i]+row[i-3])%1000000007;
if(i-4>=0)
row[i]= (row[i]+row[i-4])%1000000007;
}
row[0]=0;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT *
/
int counter;
cin>>counter;
int height; int width;
vector row;
for(int i=0; i
{
cin>>height;
cin>>width;
if(height==0||width==0)
cout<<0<
else
{
row.clear();
row.resize(width+1);
setRow(row);
cout<
}
}
return 0;
} | d*******3
发帖数: 58 | |
|
