r*******h
发帖数: 315 | 1 画给定行数和列数的grid，每次拿起画笔都是有代价的，墨水也有代价，求画一个grid
的最小成本。
自己思考了一下，DP的问题是无法建立一个转移方程，DFS也有问题，可以重复画多长
一段无法确定。 |
T******7
发帖数: 1419 | |
C****t
发帖数: 53 | 3 Assume # of grid points with odd degrees = D, then the minimum # of lifts =
D//2.
In this case, if you have m*n blocks, the number of odd degree points = 2*(m
-1) + 2*(n-1).
The minimum number of lifts should be m+n-2.
For example, you can draw the (m-1) inner horizontal lines first, next you
can draw the inner n-2 vertical lines, the last draw will be the last inner
vertical line + outer boundary.
Totally # of lifts = (m-1) +(n-2) +1 |
r*******h
发帖数: 315 | 4 哪里模糊了？求指明
【在 T******7 的大作中提到】
: 题目太模糊。
|
l****h
发帖数: 1189 | 5 墨水也有代价。即意味着有的地方可以重画，而不抬笔，是吗？ |
r*******h
发帖数: 315 | 6 赞，确实是个很有启发的思路。可以解决如果不重复画block边的情况下的最小cost，
total_cost = min_lifts * cost_per_lift + (2mn + m + n) * ink_cost_per_unit
问题是如果允许重复画block的边，cost_per_lift又比ink_cost_per_unit大太多的情
况下，最小cost就比较难搞了。
=
(m
inner
【在 C****t 的大作中提到】
: Assume # of grid points with odd degrees = D, then the minimum # of lifts =
: D//2.
: In this case, if you have m*n blocks, the number of odd degree points = 2*(m
: -1) + 2*(n-1).
: The minimum number of lifts should be m+n-2.
: For example, you can draw the (m-1) inner horizontal lines first, next you
: can draw the inner n-2 vertical lines, the last draw will be the last inner
: vertical line + outer boundary.
: Totally # of lifts = (m-1) +(n-2) +1
|
r*******h
发帖数: 315 | 7 对的，感觉这里也是难点所在，无法简单的标记visited来做backtracking
【在 l****h 的大作中提到】
: 墨水也有代价。即意味着有的地方可以重画，而不抬笔，是吗？
|
v********o
发帖数: 67 | 8 在重画cell一条边的cost比抬笔cost低的情况下，可以选择用重画来代替抬笔。
首先考虑把整幅图的四条边界间隔性地重画一遍(每隔一个边界cell重画一条边)，这样
就可以整张图中所有点都变成偶度数了。
然后想到一笔画问题可以接受一对奇度数点，还可以留一个cell边不重画，这样总共是
(2(m-1)+2(n-1))÷2-1 = m+n-3次重画，与所需的最小抬笔次数持平。
考虑到每次不得不抬笔的时候至少需要一次重画来挽回，而上面正好达到这一点，这样
是不是就是最小cost了呢？
【在 r*******h 的大作中提到】
: 赞，确实是个很有启发的思路。可以解决如果不重复画block边的情况下的最小cost，
: total_cost = min_lifts * cost_per_lift + (2mn + m + n) * ink_cost_per_unit
: 问题是如果允许重复画block的边，cost_per_lift又比ink_cost_per_unit大太多的情
: 况下，最小cost就比较难搞了。
:
: =
: (m
: inner
|
b***e
发帖数: 1419 | 9 这是中国邮路问题的推广。如果提笔的cost 是无穷大的话就退化成中国邮路问题了。
grid
【在 r*******h 的大作中提到】
: 画给定行数和列数的grid，每次拿起画笔都是有代价的，墨水也有代价，求画一个grid
: 的最小成本。
: 自己思考了一下，DP的问题是无法建立一个转移方程，DFS也有问题，可以重复画多长
: 一段无法确定。
|
r*******h
发帖数: 315 | 10 谢谢启发。3楼给出的是多笔画无重复的最小成本方案，而你提到的中国邮路问题解决
了一笔画可能有重复的最小成本方案。这两个值可以看作最终答案的上界和下界，对于
有些grid来说，可能存在多笔画有重复的最小成本解。
【在 b***e 的大作中提到】
: 这是中国邮路问题的推广。如果提笔的cost 是无穷大的话就退化成中国邮路问题了。
:
: grid
|
r*******h
发帖数: 315 | 11 你的思路有点类似9楼提到的中国邮路问题的无向图解法，需要选择重画的边，不过标
准的解法是找出所有奇度数的点，建立连通图，然后找到可以到达所有点的最小成本边
的集合，这也就是解决一笔画可能会重复的最小代价方案。
【在 v********o 的大作中提到】
: 在重画cell一条边的cost比抬笔cost低的情况下，可以选择用重画来代替抬笔。
: 首先考虑把整幅图的四条边界间隔性地重画一遍(每隔一个边界cell重画一条边)，这样
: 就可以整张图中所有点都变成偶度数了。
: 然后想到一笔画问题可以接受一对奇度数点，还可以留一个cell边不重画，这样总共是
: (2(m-1)+2(n-1))÷2-1 = m+n-3次重画，与所需的最小抬笔次数持平。
: 考虑到每次不得不抬笔的时候至少需要一次重画来挽回，而上面正好达到这一点，这样
: 是不是就是最小cost了呢？
|
C****t
发帖数: 53 | 12 It is hard to see the relationship between dp(i,j) and dp(x, y) 0<=x<=i, 0<
=y<= j.
Or it might be not feasible to use DP. |
s**i
发帖数: 220 | 13 瞎猜一下：
1) init state:
grid[1,1] = ?;
grid[2,1] = ?;
grid[1,2] = ?;
grid[2,2] = ?;
2) state transfering:
grid[m, n] = min{grid[m-1,n]+Line[m], grid[m, n-1]+line[n],grid[m-1,n-1] +
out border } |
l****h
发帖数: 1189 | 14 感觉似乎不是ＤＰ问题。
这个可以往回走的。比如抬笔代价很大的情况，可以有回走的情况。除非能证明所有回
走的情况都可以在代价相同或更小的情况下被前走替代。
【在 s**i 的大作中提到】
: 瞎猜一下：
: 1) init state:
: grid[1,1] = ?;
: grid[2,1] = ?;
: grid[1,2] = ?;
: grid[2,2] = ?;
: 2) state transfering:
: grid[m, n] = min{grid[m-1,n]+Line[m], grid[m, n-1]+line[n],grid[m-1,n-1] +
: out border }
|
