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 感觉似乎不是DP问题。
这个可以往回走的。比如抬笔代价很大的情况,可以有回走的情况。除非能证明所有回
走的情况都可以在代价相同或更小的情况下被前走替代。
【在 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 }
|