M*******a
发帖数: 1633 | 1 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
现在有点想不通这种情况怎么处理法
@@^
**^
&##
&aa |
w**z
发帖数: 8232 | 2 问问泥瓦匠？
【在 M*******a 的大作中提到】
: 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
: 现在有点想不通这种情况怎么处理法
: @@^
: **^
: &##
: &aa
|
M*******a
发帖数: 1633 | 3 人家耍题呢，不要捣乱
【在 w**z 的大作中提到】
: 问问泥瓦匠？
|
l******e
发帖数: 54 | 4 可以 DP
一行一行的来
枚举当前行的铺法 累计和上一行相容的方案数 |
M*******a
发帖数: 1633 | 5 我一上来就直着排呢？
DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了
【在 l******e 的大作中提到】
: 可以 DP
: 一行一行的来
: 枚举当前行的铺法 累计和上一行相容的方案数
|
h*******e
发帖数: 1377 | 6 长寿说的方法是正确方法的一种, 你自己试试写代码看。
【在 M*******a 的大作中提到】
: 我一上来就直着排呢？
: DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了
|
M*******a
发帖数: 1633 | 7 不会，你写个递推式看看
【在 h*******e 的大作中提到】
: 长寿说的方法是正确方法的一种, 你自己试试写代码看。
|
r**********g
发帖数: 22734 | 8 跟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也是一样。其实应该有
解析解。 |
|
a******l
发帖数: 72 | 9 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
) |
h*******e
发帖数: 1377 | 10 如果 m n 中有一个小于３０的话
for(int rowI = 0; rowI < rowNum; ++ rowI)
for(int dpI = 0; dpI < 1 << colNum; ++ dpI)
for(int colI = 0; colI < colNum; ++ colI)
{
//然后自己转移状态就行了。
３ 种情况 １ 本格占了 。
２ 本格没占 右边突出
３ 本格没占 下边突出
然后相加可能的各种情况就行了。
}
|
|
|
l******e
发帖数: 54 | 11 就是普通的状态压缩 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两个字母就算把问题解决了
|
l******e
发帖数: 54 | 12 漏了一句：铺法里 1 表示竖着 0 表示不铺或者横着
mask 超过整数范围的话就用多个整数拼接 当然已经是指数级算法了 还这么大的话要
算到死
时间还可以优化的 比如第二重循环或者预处理 check 都丢给其他大牛了
当然这题我是在 OJ 做过的 正确性就不用怀疑了 |
s********x
发帖数: 81 | 13 好像如果这个问题是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有关 |
M*******a
发帖数: 1633 | 14 你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也是一样。其实应该有
: 解析解。
|
M*******a
发帖数: 1633 | 15 这复杂度大死了吧。
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
: )
|
M*******a
发帖数: 1633 | 16 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) {
: // 上一行的铺法
|
M*******a
发帖数: 1633 | 17 还有你们这些个做法能不能handle这种螺旋状况阿
【在 M*******a 的大作中提到】
: 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
: 现在有点想不通这种情况怎么处理法
: @@^
: **^
: &##
: &aa
|
M*******a
发帖数: 1633 | 18 这道我看到过的，好理解
【在 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有关
|
g***s
发帖数: 3811 | 19 Roethlisberg 给的算法是错的。去看longlife的算法。
【在 M*******a 的大作中提到】
: 你c(m,1)什么意思c(m,n-1)什么意思，c(m,1)*c(m,n-1)什么意思都给解释下好吧
|
M*******a
发帖数: 1633 | 20 没递推式看不懂
【在 g***s 的大作中提到】
: Roethlisberg 给的算法是错的。去看longlife的算法。
|
|
|
l******e
发帖数: 54 | 21 递推式不是在 code 里吗
f[(i + 1) & 1][j] += f[i & 1][k];
i, j, k 已经解释了的
这个我做空间优化了 你把 & 1 都忽略掉好了 |
r**********g
发帖数: 22734 | 22 我也看出来了。谢，递推是错的。别看我的那贴。
【在 g***s 的大作中提到】
: Roethlisberg 给的算法是错的。去看longlife的算法。
|
M*******a
发帖数: 1633 | 23 有点明白了，就是一行行试过去，每个还没fill的位置要么横过来放要么竖过来放，最
后放满就输出，不行就回朔。
不过这个基本算back tracking把，就是类似八皇后的标准做法，不算DP把。 |
g***s
发帖数: 3811 | 24 说明还没明白。继续去理解。
★ 发自iPhone App: ChineseWeb 8.6
【在 M*******a 的大作中提到】
: 有点明白了，就是一行行试过去，每个还没fill的位置要么横过来放要么竖过来放，最
: 后放满就输出，不行就回朔。
: 不过这个基本算back tracking把，就是类似八皇后的标准做法，不算DP把。
|
M*******a
发帖数: 1633 | 25 我backtracking做不行么
【在 g***s 的大作中提到】
: 说明还没明白。继续去理解。
:
: ★ 发自iPhone App: ChineseWeb 8.6
|
c*******y
发帖数: 98 | 26 我没有明白楼上大牛们的思路，我画了个表
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。
不知道对不对。 |
c*******y
发帖数: 98 | 27 我没有明白楼上大牛们的思路，我画了个表
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。
不知道对不对。 |
c*******y
发帖数: 98 | 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。
不知道对不对。
【在 M*******a 的大作中提到】
: 没递推式看不懂
|
g***s
发帖数: 3811 | 29 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。
: 不知道对不对。
|
g***s
发帖数: 3811 | 30 yes, you can if time is not a concern.
【在 M*******a 的大作中提到】
: 我backtracking做不行么
|
|
|
M*******a
发帖数: 1633 | 31 复杂度高么？还是一样？
你复杂度多少？
【在 g***s 的大作中提到】
: yes, you can if time is not a concern.
|
g***s
发帖数: 3811 | 32 longlife都给出程序和解释了。要是还是看不懂，继续努力吧。
【在 M*******a 的大作中提到】
: 复杂度高么？还是一样？
: 你复杂度多少？
|
M*******a
发帖数: 1633 | 33 请问您这个什么OJ?
leetcode好像没有么，是不是什么俄罗斯刷题网的OJ
【在 l******e 的大作中提到】
: 漏了一句：铺法里 1 表示竖着 0 表示不铺或者横着
: mask 超过整数范围的话就用多个整数拼接 当然已经是指数级算法了 还这么大的话要
: 算到死
: 时间还可以优化的 比如第二重循环或者预处理 check 都丢给其他大牛了
: 当然这题我是在 OJ 做过的 正确性就不用怀疑了
|
m********6
发帖数: 58 | 34 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)之类的东西有没有？
: 然后最好给解释下行不
|
l******e
发帖数: 54 | 35 楼上大牛介绍的是“刷表法” 由上一行刷下一行
我给出的例程其实是从当前行找上一行的“填表法” 可自行 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.
|
l******e
发帖数: 54 | |
M*******a
发帖数: 1633 | 37 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
现在有点想不通这种情况怎么处理法
@@^
**^
&##
&aa |
w**z
发帖数: 8232 | 38 问问泥瓦匠？
【在 M*******a 的大作中提到】
: 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
: 现在有点想不通这种情况怎么处理法
: @@^
: **^
: &##
: &aa
|
M*******a
发帖数: 1633 | 39 人家耍题呢，不要捣乱
【在 w**z 的大作中提到】
: 问问泥瓦匠？
|
l******e
发帖数: 54 | 40 可以 DP
一行一行的来
枚举当前行的铺法 累计和上一行相容的方案数 |
|
|
M*******a
发帖数: 1633 | 41 我一上来就直着排呢？
DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了
【在 l******e 的大作中提到】
: 可以 DP
: 一行一行的来
: 枚举当前行的铺法 累计和上一行相容的方案数
|
h*******e
发帖数: 1377 | 42 长寿说的方法是正确方法的一种, 你自己试试写代码看。
【在 M*******a 的大作中提到】
: 我一上来就直着排呢？
: DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了
|
M*******a
发帖数: 1633 | 43 不会，你写个递推式看看
【在 h*******e 的大作中提到】
: 长寿说的方法是正确方法的一种, 你自己试试写代码看。
|
r**********g
发帖数: 22734 | 44 跟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也是一样。其实应该有
解析解。 |
a******l
发帖数: 72 | 45 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
) |
h*******e
发帖数: 1377 | 46 如果 m n 中有一个小于３０的话
for(int rowI = 0; rowI < rowNum; ++ rowI)
for(int dpI = 0; dpI < 1 << colNum; ++ dpI)
for(int colI = 0; colI < colNum; ++ colI)
{
//然后自己转移状态就行了。
３ 种情况 １ 本格占了 。
２ 本格没占 右边突出
３ 本格没占 下边突出
然后相加可能的各种情况就行了。
}
|
l******e
发帖数: 54 | 47 就是普通的状态压缩 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两个字母就算把问题解决了
|
l******e
发帖数: 54 | 48 漏了一句：铺法里 1 表示竖着 0 表示不铺或者横着
mask 超过整数范围的话就用多个整数拼接 当然已经是指数级算法了 还这么大的话要
算到死
时间还可以优化的 比如第二重循环或者预处理 check 都丢给其他大牛了
当然这题我是在 OJ 做过的 正确性就不用怀疑了 |
s********x
发帖数: 81 | 49 好像如果这个问题是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有关 |
M*******a
发帖数: 1633 | 50 你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也是一样。其实应该有
: 解析解。
|
|
|
M*******a
发帖数: 1633 | 51 这复杂度大死了吧。
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
: )
|
M*******a
发帖数: 1633 | 52 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) {
: // 上一行的铺法
|
M*******a
发帖数: 1633 | 53 还有你们这些个做法能不能handle这种螺旋状况阿
【在 M*******a 的大作中提到】
: 就是用1*2的瓷砖铺地，N*M的地板有几种铺法
: 现在有点想不通这种情况怎么处理法
: @@^
: **^
: &##
: &aa
|
M*******a
发帖数: 1633 | 54 这道我看到过的，好理解
【在 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有关
|
g***s
发帖数: 3811 | 55 Roethlisberg 给的算法是错的。去看longlife的算法。
【在 M*******a 的大作中提到】
: 你c(m,1)什么意思c(m,n-1)什么意思，c(m,1)*c(m,n-1)什么意思都给解释下好吧
|
M*******a
发帖数: 1633 | 56 没递推式看不懂
【在 g***s 的大作中提到】
: Roethlisberg 给的算法是错的。去看longlife的算法。
|
l******e
发帖数: 54 | 57 递推式不是在 code 里吗
f[(i + 1) & 1][j] += f[i & 1][k];
i, j, k 已经解释了的
这个我做空间优化了 你把 & 1 都忽略掉好了 |
r**********g
发帖数: 22734 | 58 我也看出来了。谢，递推是错的。别看我的那贴。
【在 g***s 的大作中提到】
: Roethlisberg 给的算法是错的。去看longlife的算法。
|
M*******a
发帖数: 1633 | 59 有点明白了，就是一行行试过去，每个还没fill的位置要么横过来放要么竖过来放，最
后放满就输出，不行就回朔。
不过这个基本算back tracking把，就是类似八皇后的标准做法，不算DP把。 |
g***s
发帖数: 3811 | 60 说明还没明白。继续去理解。
★ 发自iPhone App: ChineseWeb 8.6
【在 M*******a 的大作中提到】
: 有点明白了，就是一行行试过去，每个还没fill的位置要么横过来放要么竖过来放，最
: 后放满就输出，不行就回朔。
: 不过这个基本算back tracking把，就是类似八皇后的标准做法，不算DP把。
|
|
|
M*******a
发帖数: 1633 | 61 我backtracking做不行么
【在 g***s 的大作中提到】
: 说明还没明白。继续去理解。
:
: ★ 发自iPhone App: ChineseWeb 8.6
|
c*******y
发帖数: 98 | 62 我没有明白楼上大牛们的思路，我画了个表
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。
不知道对不对。 |
c*******y
发帖数: 98 | 63 我没有明白楼上大牛们的思路，我画了个表
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。
不知道对不对。 |
c*******y
发帖数: 98 | 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。
不知道对不对。
【在 M*******a 的大作中提到】
: 没递推式看不懂
|
g***s
发帖数: 3811 | 65 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。
: 不知道对不对。
|
g***s
发帖数: 3811 | 66 yes, you can if time is not a concern.
【在 M*******a 的大作中提到】
: 我backtracking做不行么
|
M*******a
发帖数: 1633 | 67 复杂度高么？还是一样？
你复杂度多少？
【在 g***s 的大作中提到】
: yes, you can if time is not a concern.
|
g***s
发帖数: 3811 | 68 longlife都给出程序和解释了。要是还是看不懂，继续努力吧。
【在 M*******a 的大作中提到】
: 复杂度高么？还是一样？
: 你复杂度多少？
|
M*******a
发帖数: 1633 | 69 请问您这个什么OJ?
leetcode好像没有么，是不是什么俄罗斯刷题网的OJ
【在 l******e 的大作中提到】
: 漏了一句：铺法里 1 表示竖着 0 表示不铺或者横着
: mask 超过整数范围的话就用多个整数拼接 当然已经是指数级算法了 还这么大的话要
: 算到死
: 时间还可以优化的 比如第二重循环或者预处理 check 都丢给其他大牛了
: 当然这题我是在 OJ 做过的 正确性就不用怀疑了
|
m********6
发帖数: 58 | 70 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)之类的东西有没有？
: 然后最好给解释下行不
|
|
|
l******e
发帖数: 54 | 71 楼上大牛介绍的是“刷表法” 由上一行刷下一行
我给出的例程其实是从当前行找上一行的“填表法” 可自行 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.
|
l******e
发帖数: 54 | |
f**********t
发帖数: 1001 | 73 写个暴力的，要求状态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) {
: // 上一行的铺法
|
a***e
发帖数: 413 | 74 好奇问下，这是哪个OJ里面的呢？没在leetcode上看到啊？ |
I**********s
发帖数: 441 | 75 这样如何:
如果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
|
p**t
发帖数: 157 | 76 这个应该不对
存在一些排法 可以铺满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). 如果第一块砖是竖排的, 那么最后一块也是:
: | ... |
: | ... |
: 如果第一一块砖是横排的, 那么是这样:
: -- ...
: -- ...
|
