老师买表
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
由于方老师出色的专题讲座,他的名气迅速扩散到全国各地,并通过各地的讲座赚到了很多钱,鉴于现在盛行买表,于是方老师带上了一个H×W的盒子去买表,我们假设每一个表占1×2或者2×1的空间,问方老师有多少种放置表的方式,把这个盒子填满。
Input
输入有多组数据
每组数据占一行,每一行有2个正整数H,W,(1≤H,W≤11)
Output
对于每组测试数据输出1个整数,表示该测试数据的答案
Sample input and output
Sample InputSample Output
2 10
3 3 89
0
Source
2014 UESTC Training for Dynamic Programming
解题报告
跟冬马党那题一样~,f(i,j)表示第i行摆成j样子的时候的总方案数.
转移的时候从最右边往最左边dp(正好跟二进制一样~).转移一共三种
假设正在转移第 pos 位,同时目前的摆放状态是 val (第 pos - 1 -- 第 0 位是这行的状态 , 第pos - 第 w 位还是上一行的状态)
if (val >> pos & 1 ) //上一行的这里摆了
转移至 val & ~(1 << pos) //这里可以不摆
if ( pos 不是最左边 && val >> (pos+1) & 1 ) // 现在可以左放
转移至 val ; //值是一样,但是含义不一样了哦
else
转移至 val | (1 << pos) //竖着放
这样就解决了~~
代码用了滚动数组,优化了空间复杂度
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <algorithm>
5 typedef
long long ll;
6 using namespace std;
7 ll f[
2][
1 <<
11];
8 int h,w,cur =
0;
9
10 void dfs(
int pos,
int val,ll add)
11 {
12 if (pos ==
w)
13 f[cur][val] +=
add;
14 else
15 {
16 if (val >> pos &
1)
17 {
18 dfs(pos+
1,val & ~(
1 << pos) , add);
//不放
19 if (pos < w-
1 && val >> (pos+
1) &
1)
//左放
20 dfs(pos+
2,val,add);
21 }
22 else
23 dfs(pos+
1,val | (
1 << pos),add );
//竖着放
24 }
25 }
26
27 int main(
int argc,
char *
argv[])
28 {
29 while(~scanf(
"%d%d",&h,&
w))
30 {
31 memset(f,
0,
sizeof(f));
32 dfs(
0,(
1 << w)-
1,
1);
33 for(
int i =
1 ; i < h ; ++
i)
34 {
35 cur ^=
1;
36 for(
int i =
0 ; i < (
1 << w) ; ++ i) f[cur][i] =
0;
37 for(
int j =
0 ; j < (
1 << w) ; ++
j)
38 dfs(
0,j,f[cur^
1][j]);
39 }
40 printf(
"%lld\n",f[cur][(
1<<w)-
1]);
41 }
42 return 0;
43 }
转载于:https://www.cnblogs.com/Xiper/p/4480769.html
相关资源:垃圾分类数据集及代码