logo
Redian新闻
>未名空间
>Parenting - 为人父母
>
现在的小孩 相貌上越来越好看了
avatar
现在的小孩 相貌上越来越好看了# Parenting - 为人父母
M*a
1 楼
就是用1*2的瓷砖铺地，N*M的地板有几种铺法
现在有点想不通这种情况怎么处理法
@@^
**^
#
&aa
avatar
a*r
2 楼
发现现在的小孩子真的是越长越漂亮了，一个个肤色白打扮好漂亮的很，不像老一辈，那时候的小孩个顶个的丑，脏。
avatar
w*z
3 楼
问问泥瓦匠？

【在 M*******a 的大作中提到】
: 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
: 现在有点想不通这种情况怎么处理法
: @@^
: **^
: #
: &aa
avatar
h*b
4 楼
混血的都敢贴出来, 够胆 :p
avatar
M*a
5 楼
人家耍题呢，不要捣乱

【在 w**z 的大作中提到】
: 问问泥瓦匠？
avatar
l*e
6 楼
可以 DP
一行一行的来
枚举当前行的铺法 累计和上一行相容的方案数
avatar
M*a
7 楼
我一上来就直着排呢？
DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了

【在 l******e 的大作中提到】
: 可以 DP
: 一行一行的来
: 枚举当前行的铺法 累计和上一行相容的方案数
avatar
h*e
8 楼
长寿说的方法是正确方法的一种, 你自己试试写代码看。

【在 M*******a 的大作中提到】
: 我一上来就直着排呢？
: DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了
avatar
M*a
9 楼
不会，你写个递推式看看

【在 h*******e 的大作中提到】
: 长寿说的方法是正确方法的一种, 你自己试试写代码看。
avatar
r*g
10 楼
跟dp有啥关系？dp是优化算法，这就是简单的divide and conquer.。对m*n的平面，总
数c(m,n)=c(m, 1) * c(m, n-1) + c(m, 2) * c(m, n-2). 对n也是一样。其实应该有
解析解。
avatar
a*l
11 楼
recursion, at each frontier location, layout a 1x2 or 2x1 tile at the
current location,
mark the locations occupied (2 locations) by the tile, recursively call,
like dfs recursion
bottom out case, all marked tiled! (M*N must be even, otherwise, no solution
)
avatar
h*e
12 楼
如果 m n 中有一个小于３０的话
for(int rowI = 0; rowI < rowNum; ++ rowI)
for(int dpI = 0; dpI < 1 << colNum; ++ dpI)
for(int colI = 0; colI < colNum; ++ colI)
{
//然后自己转移状态就行了。
３　种情况　１　本格占了　。
２　本格没占　右边突出
３　本格没占　下边突出
然后相加可能的各种情况就行了。
}
avatar
l*e
13 楼
就是普通的状态压缩 DP 或者递推
我都把算法描述出来了 看不懂只好丢给你个程序了
int mask = (1 << m) - 1;
f[0][0] = 1;
// 一行一行的来
for (int i = 0; i < n; ++i) {
FILL(f[(i + 1) & 1], 0);
// 枚举本行的铺法
for (int j = 0; j <= mask; ++j) {
// 上一行的铺法
for (int k = 0; k <= mask; ++k) {
// 检查相容
if (check(j, k, mask)) {
// 累加
f[(i + 1) & 1][j] += f[i & 1][k];
}
}
}
}
// 输出解
cout << f[n & 1][0] << endl;
bool check(int j, int k, int mask) {
if (j & k) return false;
int state = ~(j | k) & mask;
while (state) {
if (state & 1) {
state >>= 1;
if (!(state & 1)) return false;
}
state >>= 1;
}
return true;
}

【在 M*******a 的大作中提到】
: 我一上来就直着排呢？
: DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了
avatar
l*e
14 楼
漏了一句：铺法里 1 表示竖着 0 表示不铺或者横着
mask 超过整数范围的话就用多个整数拼接 当然已经是指数级算法了 还这么大的话要
算到死
时间还可以优化的 比如第二重循环或者预处理 check 都丢给其他大牛了
当然这题我是在 OJ 做过的 正确性就不用怀疑了
avatar
s*x
15 楼
好像如果这个问题是M*2，解法是fibonacci数列。
不知道这一点是否可以用来优化M*N。
铺法里 1 表示竖着 0表示横着
0 0x2 1 (nothing)
1 1x2 1 (1)
2 2x2 2 (11, 00)
3 3x2 3 (111, 100, 001)
4 4x2 5 (1111, 1001, 0011, 1100, 0000)
f(m) = f(m-1) + f(m-2)
f(m-1) 只和1有关
f(m-2) 只和00有关
avatar
M*a
16 楼
你c(m,1)什么意思c(m,n-1)什么意思，c(m,1)*c(m,n-1)什么意思都给解释下好吧

【在 r**********g 的大作中提到】
: 跟dp有啥关系？dp是优化算法，这就是简单的divide and conquer.。对m*n的平面，总
: 数c(m,n)=c(m, 1) * c(m, n-1) + c(m, 2) * c(m, n-2). 对n也是一样。其实应该有
: 解析解。
avatar
M*a
17 楼
这复杂度大死了吧。

solution

【在 a******l 的大作中提到】
: recursion, at each frontier location, layout a 1x2 or 2x1 tile at the
: current location,
: mark the locations occupied (2 locations) by the tile, recursively call,
: like dfs recursion
: bottom out case, all marked tiled! (M*N must be even, otherwise, no solution
: )
avatar
M*a
18 楼
DP的话写个F(n)=xxxxF(n-1)之类的东西有没有？
然后最好给解释下行不

【在 l******e 的大作中提到】
: 就是普通的状态压缩 DP 或者递推
: 我都把算法描述出来了 看不懂只好丢给你个程序了
: int mask = (1 << m) - 1;
: f[0][0] = 1;
: // 一行一行的来
: for (int i = 0; i < n; ++i) {
: FILL(f[(i + 1) & 1], 0);
: // 枚举本行的铺法
: for (int j = 0; j <= mask; ++j) {
: // 上一行的铺法
avatar
M*a
19 楼
还有你们这些个做法能不能handle这种螺旋状况阿

【在 M*******a 的大作中提到】
: 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
: 现在有点想不通这种情况怎么处理法
: @@^
: **^
: #
: &aa
avatar
M*a
20 楼
这道我看到过的，好理解

【在 s********x 的大作中提到】
: 好像如果这个问题是M*2，解法是fibonacci数列。
: 不知道这一点是否可以用来优化M*N。
: 铺法里 1 表示竖着 0表示横着
: 0 0x2 1 (nothing)
: 1 1x2 1 (1)
: 2 2x2 2 (11, 00)
: 3 3x2 3 (111, 100, 001)
: 4 4x2 5 (1111, 1001, 0011, 1100, 0000)
: f(m) = f(m-1) + f(m-2)
: f(m-1) 只和1有关
avatar
g*s
21 楼
Roethlisberg 给的算法是错的。去看longlife的算法。

【在 M*******a 的大作中提到】
: 你c(m,1)什么意思c(m,n-1)什么意思，c(m,1)*c(m,n-1)什么意思都给解释下好吧
avatar
M*a
22 楼
没递推式看不懂

【在 g***s 的大作中提到】
: Roethlisberg 给的算法是错的。去看longlife的算法。
avatar
l*e
23 楼
递推式不是在 code 里吗
f[(i + 1) & 1][j] += f[i & 1][k];
i, j, k 已经解释了的
这个我做空间优化了 你把 & 1 都忽略掉好了
avatar
r*g
24 楼
我也看出来了。谢，递推是错的。别看我的那贴。

【在 g***s 的大作中提到】
: Roethlisberg 给的算法是错的。去看longlife的算法。
avatar
M*a
25 楼
有点明白了，就是一行行试过去，每个还没fill的位置要么横过来放要么竖过来放，最
后放满就输出，不行就回朔。
不过这个基本算back tracking把，就是类似八皇后的标准做法，不算DP把。
avatar
g*s
26 楼
说明还没明白。继续去理解。

★ 发自iPhone App: ChineseWeb 8.6

【在 M*******a 的大作中提到】
: 有点明白了，就是一行行试过去，每个还没fill的位置要么横过来放要么竖过来放，最
: 后放满就输出，不行就回朔。
: 不过这个基本算back tracking把，就是类似八皇后的标准做法，不算DP把。
avatar
M*a
27 楼
我backtracking做不行么

【在 g***s 的大作中提到】
: 说明还没明白。继续去理解。
:
: ★ 发自iPhone App: ChineseWeb 8.6
avatar
c*y
28 楼
我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。
avatar
c*y
29 楼
我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。
avatar
c*y
30 楼
我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。

【在 M*******a 的大作中提到】
: 没递推式看不懂
avatar
g*s
31 楼
no.

【在 c*******y 的大作中提到】
: 我没有明白楼上大牛们的思路，我画了个表
: 0 1 0 1 0 1 0 1
: 1 2 3 4 5 6 7 8
: 0 3 0 7 0 11 0 15
: 1 4 7 14 21 32 43 58
: 初始化第一行0 1 0 1 ...
: 第一列0 1 0 1...
: 递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
: 中间遇到(row+1)*(col+1)为奇数的，设为0。
: 不知道对不对。
avatar
g*s
32 楼
yes, you can if time is not a concern.

【在 M*******a 的大作中提到】
: 我backtracking做不行么
avatar
M*a
33 楼
复杂度高么？还是一样？
你复杂度多少？

【在 g***s 的大作中提到】
: yes, you can if time is not a concern.
avatar
g*s
34 楼
longlife都给出程序和解释了。要是还是看不懂，继续努力吧。

【在 M*******a 的大作中提到】
: 复杂度高么？还是一样？
: 你复杂度多少？
avatar
M*a
35 楼
请问您这个什么OJ?
leetcode好像没有么，是不是什么俄罗斯刷题网的OJ

【在 l******e 的大作中提到】
: 漏了一句：铺法里 1 表示竖着 0 表示不铺或者横着
: mask 超过整数范围的话就用多个整数拼接 当然已经是指数级算法了 还这么大的话要
: 算到死
: 时间还可以优化的 比如第二重循环或者预处理 check 都丢给其他大牛了
: 当然这题我是在 OJ 做过的 正确性就不用怀疑了
avatar
m*6
36 楼
f[n&1][mask] tells you what squares in the current level are already filled.
f[n+1 & 1][mask] calculates different ways to fill the current level.
f[0][0] is the initial condition. When you are trying to fill the first
level, the previous level is flat and the current level is empty.
adding if (f[n&1][j] == 0) continue; is not a bad optimization.

【在 M*******a 的大作中提到】
: DP的话写个F(n)=xxxxF(n-1)之类的东西有没有？
: 然后最好给解释下行不
avatar
l*e
37 楼
楼上大牛介绍的是“刷表法” 由上一行刷下一行
我给出的例程其实是从当前行找上一行的“填表法” 可自行 Google 这两种方法的更
多信息
更喜欢刷表法 加 continue 是一个很大的优化 另外还需要改的是递推式里的 j 和 k
要换一下位置其他不变
f[(i + 1) & 1][k] += f[i & 1][j];
最后变成：
int mask = (1 << m) - 1;
f[0][0] = 1;
for (int i = 0; i < n; ++i) {
FILL(f[(i + 1) & 1], 0);
for (int j = 0; j <= mask; ++j) {
if (f[i & 1][j] == 0) continue;
for (int k = 0; k <= mask; ++k) {
if (check(j, k, mask)) {
f[(i + 1) & 1][k] += f[i & 1][j];
}
}
}
}

filled.

【在 m********6 的大作中提到】
: f[n&1][mask] tells you what squares in the current level are already filled.
: f[n+1 & 1][mask] calculates different ways to fill the current level.
: f[0][0] is the initial condition. When you are trying to fill the first
: level, the previous level is flat and the current level is empty.
: adding if (f[n&1][j] == 0) continue; is not a bad optimization.
avatar
M*a
39 楼
就是用1*2的瓷砖铺地，N*M的地板有几种铺法
现在有点想不通这种情况怎么处理法
@@^
**^
#
&aa
avatar
w*z
40 楼
问问泥瓦匠？

【在 M*******a 的大作中提到】
: 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
: 现在有点想不通这种情况怎么处理法
: @@^
: **^
: #
: &aa
avatar
M*a
41 楼
人家耍题呢，不要捣乱

【在 w**z 的大作中提到】
: 问问泥瓦匠？
avatar
l*e
42 楼
可以 DP
一行一行的来
枚举当前行的铺法 累计和上一行相容的方案数
avatar
M*a
43 楼
我一上来就直着排呢？
DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了

【在 l******e 的大作中提到】
: 可以 DP
: 一行一行的来
: 枚举当前行的铺法 累计和上一行相容的方案数
avatar
h*e
44 楼
长寿说的方法是正确方法的一种, 你自己试试写代码看。

【在 M*******a 的大作中提到】
: 我一上来就直着排呢？
: DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了
avatar
M*a
45 楼
不会，你写个递推式看看

【在 h*******e 的大作中提到】
: 长寿说的方法是正确方法的一种, 你自己试试写代码看。
avatar
r*g
46 楼
跟dp有啥关系？dp是优化算法，这就是简单的divide and conquer.。对m*n的平面，总
数c(m,n)=c(m, 1) * c(m, n-1) + c(m, 2) * c(m, n-2). 对n也是一样。其实应该有
解析解。
avatar
a*l
47 楼
recursion, at each frontier location, layout a 1x2 or 2x1 tile at the
current location,
mark the locations occupied (2 locations) by the tile, recursively call,
like dfs recursion
bottom out case, all marked tiled! (M*N must be even, otherwise, no solution
)
avatar
h*e
48 楼
如果 m n 中有一个小于３０的话
for(int rowI = 0; rowI < rowNum; ++ rowI)
for(int dpI = 0; dpI < 1 << colNum; ++ dpI)
for(int colI = 0; colI < colNum; ++ colI)
{
//然后自己转移状态就行了。
３　种情况　１　本格占了　。
２　本格没占　右边突出
３　本格没占　下边突出
然后相加可能的各种情况就行了。
}
avatar
l*e
49 楼
就是普通的状态压缩 DP 或者递推
我都把算法描述出来了 看不懂只好丢给你个程序了
int mask = (1 << m) - 1;
f[0][0] = 1;
// 一行一行的来
for (int i = 0; i < n; ++i) {
FILL(f[(i + 1) & 1], 0);
// 枚举本行的铺法
for (int j = 0; j <= mask; ++j) {
// 上一行的铺法
for (int k = 0; k <= mask; ++k) {
// 检查相容
if (check(j, k, mask)) {
// 累加
f[(i + 1) & 1][j] += f[i & 1][k];
}
}
}
}
// 输出解
cout << f[n & 1][0] << endl;
bool check(int j, int k, int mask) {
if (j & k) return false;
int state = ~(j | k) & mask;
while (state) {
if (state & 1) {
state >>= 1;
if (!(state & 1)) return false;
}
state >>= 1;
}
return true;
}

【在 M*******a 的大作中提到】
: 我一上来就直着排呢？
: DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了
avatar
l*e
50 楼
漏了一句：铺法里 1 表示竖着 0 表示不铺或者横着
mask 超过整数范围的话就用多个整数拼接 当然已经是指数级算法了 还这么大的话要
算到死
时间还可以优化的 比如第二重循环或者预处理 check 都丢给其他大牛了
当然这题我是在 OJ 做过的 正确性就不用怀疑了
avatar
s*x
51 楼
好像如果这个问题是M*2，解法是fibonacci数列。
不知道这一点是否可以用来优化M*N。
铺法里 1 表示竖着 0表示横着
0 0x2 1 (nothing)
1 1x2 1 (1)
2 2x2 2 (11, 00)
3 3x2 3 (111, 100, 001)
4 4x2 5 (1111, 1001, 0011, 1100, 0000)
f(m) = f(m-1) + f(m-2)
f(m-1) 只和1有关
f(m-2) 只和00有关
avatar
M*a
52 楼
你c(m,1)什么意思c(m,n-1)什么意思，c(m,1)*c(m,n-1)什么意思都给解释下好吧

【在 r**********g 的大作中提到】
: 跟dp有啥关系？dp是优化算法，这就是简单的divide and conquer.。对m*n的平面，总
: 数c(m,n)=c(m, 1) * c(m, n-1) + c(m, 2) * c(m, n-2). 对n也是一样。其实应该有
: 解析解。
avatar
M*a
53 楼
这复杂度大死了吧。

solution

【在 a******l 的大作中提到】
: recursion, at each frontier location, layout a 1x2 or 2x1 tile at the
: current location,
: mark the locations occupied (2 locations) by the tile, recursively call,
: like dfs recursion
: bottom out case, all marked tiled! (M*N must be even, otherwise, no solution
: )
avatar
M*a
54 楼
DP的话写个F(n)=xxxxF(n-1)之类的东西有没有？
然后最好给解释下行不

【在 l******e 的大作中提到】
: 就是普通的状态压缩 DP 或者递推
: 我都把算法描述出来了 看不懂只好丢给你个程序了
: int mask = (1 << m) - 1;
: f[0][0] = 1;
: // 一行一行的来
: for (int i = 0; i < n; ++i) {
: FILL(f[(i + 1) & 1], 0);
: // 枚举本行的铺法
: for (int j = 0; j <= mask; ++j) {
: // 上一行的铺法
avatar
M*a
55 楼
还有你们这些个做法能不能handle这种螺旋状况阿

【在 M*******a 的大作中提到】
: 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
: 现在有点想不通这种情况怎么处理法
: @@^
: **^
: #
: &aa
avatar
M*a
56 楼
这道我看到过的，好理解

【在 s********x 的大作中提到】
: 好像如果这个问题是M*2，解法是fibonacci数列。
: 不知道这一点是否可以用来优化M*N。
: 铺法里 1 表示竖着 0表示横着
: 0 0x2 1 (nothing)
: 1 1x2 1 (1)
: 2 2x2 2 (11, 00)
: 3 3x2 3 (111, 100, 001)
: 4 4x2 5 (1111, 1001, 0011, 1100, 0000)
: f(m) = f(m-1) + f(m-2)
: f(m-1) 只和1有关
avatar
g*s
57 楼
Roethlisberg 给的算法是错的。去看longlife的算法。

【在 M*******a 的大作中提到】
: 你c(m,1)什么意思c(m,n-1)什么意思，c(m,1)*c(m,n-1)什么意思都给解释下好吧
avatar
M*a
58 楼
没递推式看不懂

【在 g***s 的大作中提到】
: Roethlisberg 给的算法是错的。去看longlife的算法。
avatar
l*e
59 楼
递推式不是在 code 里吗
f[(i + 1) & 1][j] += f[i & 1][k];
i, j, k 已经解释了的
这个我做空间优化了 你把 & 1 都忽略掉好了
avatar
r*g
60 楼
我也看出来了。谢，递推是错的。别看我的那贴。

【在 g***s 的大作中提到】
: Roethlisberg 给的算法是错的。去看longlife的算法。
avatar
M*a
61 楼
有点明白了，就是一行行试过去，每个还没fill的位置要么横过来放要么竖过来放，最
后放满就输出，不行就回朔。
不过这个基本算back tracking把，就是类似八皇后的标准做法，不算DP把。
avatar
g*s
62 楼
说明还没明白。继续去理解。

★ 发自iPhone App: ChineseWeb 8.6

【在 M*******a 的大作中提到】
: 有点明白了，就是一行行试过去，每个还没fill的位置要么横过来放要么竖过来放，最
: 后放满就输出，不行就回朔。
: 不过这个基本算back tracking把，就是类似八皇后的标准做法，不算DP把。
avatar
M*a
63 楼
我backtracking做不行么

【在 g***s 的大作中提到】
: 说明还没明白。继续去理解。
:
: ★ 发自iPhone App: ChineseWeb 8.6
avatar
c*y
64 楼
我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。
avatar
c*y
65 楼
我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。
avatar
c*y
66 楼
我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。

【在 M*******a 的大作中提到】
: 没递推式看不懂
avatar
g*s
67 楼
no.

【在 c*******y 的大作中提到】
: 我没有明白楼上大牛们的思路，我画了个表
: 0 1 0 1 0 1 0 1
: 1 2 3 4 5 6 7 8
: 0 3 0 7 0 11 0 15
: 1 4 7 14 21 32 43 58
: 初始化第一行0 1 0 1 ...
: 第一列0 1 0 1...
: 递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
: 中间遇到(row+1)*(col+1)为奇数的，设为0。
: 不知道对不对。
avatar
g*s
68 楼
yes, you can if time is not a concern.

【在 M*******a 的大作中提到】
: 我backtracking做不行么
avatar
M*a
69 楼
复杂度高么？还是一样？
你复杂度多少？

【在 g***s 的大作中提到】
: yes, you can if time is not a concern.
avatar
g*s
70 楼
longlife都给出程序和解释了。要是还是看不懂，继续努力吧。

【在 M*******a 的大作中提到】
: 复杂度高么？还是一样？
: 你复杂度多少？
avatar
M*a
71 楼
请问您这个什么OJ?
leetcode好像没有么，是不是什么俄罗斯刷题网的OJ

【在 l******e 的大作中提到】
: 漏了一句：铺法里 1 表示竖着 0 表示不铺或者横着
: mask 超过整数范围的话就用多个整数拼接 当然已经是指数级算法了 还这么大的话要
: 算到死
: 时间还可以优化的 比如第二重循环或者预处理 check 都丢给其他大牛了
: 当然这题我是在 OJ 做过的 正确性就不用怀疑了
avatar
m*6
72 楼
f[n&1][mask] tells you what squares in the current level are already filled.
f[n+1 & 1][mask] calculates different ways to fill the current level.
f[0][0] is the initial condition. When you are trying to fill the first
level, the previous level is flat and the current level is empty.
adding if (f[n&1][j] == 0) continue; is not a bad optimization.

【在 M*******a 的大作中提到】
: DP的话写个F(n)=xxxxF(n-1)之类的东西有没有？
: 然后最好给解释下行不
avatar
l*e
73 楼
楼上大牛介绍的是“刷表法” 由上一行刷下一行
我给出的例程其实是从当前行找上一行的“填表法” 可自行 Google 这两种方法的更
多信息
更喜欢刷表法 加 continue 是一个很大的优化 另外还需要改的是递推式里的 j 和 k
要换一下位置其他不变
f[(i + 1) & 1][k] += f[i & 1][j];
最后变成：
int mask = (1 << m) - 1;
f[0][0] = 1;
for (int i = 0; i < n; ++i) {
FILL(f[(i + 1) & 1], 0);
for (int j = 0; j <= mask; ++j) {
if (f[i & 1][j] == 0) continue;
for (int k = 0; k <= mask; ++k) {
if (check(j, k, mask)) {
f[(i + 1) & 1][k] += f[i & 1][j];
}
}
}
}

filled.

【在 m********6 的大作中提到】
: f[n&1][mask] tells you what squares in the current level are already filled.
: f[n+1 & 1][mask] calculates different ways to fill the current level.
: f[0][0] is the initial condition. When you are trying to fill the first
: level, the previous level is flat and the current level is empty.
: adding if (f[n&1][j] == 0) continue; is not a bad optimization.
avatar
f*t
75 楼
写个暴力的，要求状态DP的地方高攀不起
void NumOfBoardLayouts(vector> &board, size_t x, size_t y, int
*res) {
//for 1 * 2 board
size_t row = board.size();
size_t col = board[0].size();
if (x == row) {
++*res;
return;
}
for (size_t i = x; i < row; ++i) {
for (size_t k = y; k < col; ++k) {
if (board[i][k] == true) {
continue;
} else {
if (k + 1 < col && board[i][k + 1] == false) {
board[i][k] = true;
board[i][k + 1] = true;
NumOfBoardLayouts(board, i + (k + 2) / col, (k + 2) % col, res);
board[i][k] = false;
board[i][k + 1] = false;
}
if (i + 1 < row && board[i + 1][k] == false) {
board[i][k] = true;
board[i + 1][k] = true;
NumOfBoardLayouts(board, i + (k + 1) / col, (k + 1) % col, res);
board[i][k] = false;
board[i + 1][k] = false;
}
}
}
}
}

【在 l******e 的大作中提到】
: 就是普通的状态压缩 DP 或者递推
: 我都把算法描述出来了 看不懂只好丢给你个程序了
: int mask = (1 << m) - 1;
: f[0][0] = 1;
: // 一行一行的来
: for (int i = 0; i < n; ++i) {
: FILL(f[(i + 1) & 1], 0);
: // 枚举本行的铺法
: for (int j = 0; j <= mask; ++j) {
: // 上一行的铺法
avatar
a*e
76 楼
好奇问下，这是哪个OJ里面的呢？没在leetcode上看到啊？
avatar
I*s
77 楼
这样如何:
如果N和M都是奇数, 显然不可能, 所以至少一个是偶数. 假设M是偶数. 铺法总数
f(N, M) = c1 * f(N-1, M) + c2 * f(N-2, M)
显然c1 = 1, 因为只有一种铺法[--][--][--]...
对于c2, 铺法c2 = f(2, M). 如果第一块砖是竖排的, 那么最后一块也是:
| ... |
| ... |
如果第一一块砖是横排的, 那么是这样:
-- ...
-- ...
因此, c2 = f(2, M) = f(2, M-2) + f(2, M-2) = 2 * f(2, M-2), 初始条件f(2,2) =
2. 得到c2 = f(2, M) = 2^(M/2). 即f(2,2) = 2, f(2,4) = 2^2 = 4, f(2,6) = 2^3
= 8 ...
所以:
f(N, M) = f(N-1, M) + 2^(M/2) * f(N-2, M), where M is even.

【在 M*******a 的大作中提到】
: 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
: 现在有点想不通这种情况怎么处理法
: @@^
: **^
: #
: &aa
avatar
p*t
78 楼
这个应该不对
存在一些排法 可以铺满M*N， 但是其前n-2行是不满的

【在 I**********s 的大作中提到】
: 这样如何:
: 如果N和M都是奇数, 显然不可能, 所以至少一个是偶数. 假设M是偶数. 铺法总数
: f(N, M) = c1 * f(N-1, M) + c2 * f(N-2, M)
: 显然c1 = 1, 因为只有一种铺法[--][--][--]...
: 对于c2, 铺法c2 = f(2, M). 如果第一块砖是竖排的, 那么最后一块也是:
: | ... |
: | ... |
: 如果第一一块砖是横排的, 那么是这样:
: -- ...
: -- ...
相关阅读
请问有没有想转让中文儿童故事书的？这些小孩真聪明乱码加不能登陆，大家有这个问题吗？女儿总是爸爸的贴心小恋人密苏里大学申请人数下降 (转载)baby，我该拿什么来保护你John McCain: Salute to a Communist数学家教厕所问题：今天去很多网站支持了北卡 (转载)要孩子之前一定要做好这些思想准备！家长们长点心吧，不要随便给孩子剪睫毛问大家一条英文grammar题Re: 你在哪个格格里？ (转载)意外怀孕，这孩子是留还是不留请问哪里有英语点读机卖？【求助】孩子哭的时候要不要哄请大家帮忙看看，这两个大学怎么选？回国需要加打什么疫苗吗当前亚裔AA的斗争方向 (转载)宝宝一哭就喂奶？NO，要学会科学辨别婴儿哭
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。