r******y
发帖数: 780 | 1 题目的意思是这样，就是有N根木头， 知道每跟木头的高度，然后一个人站在第一根木
头要跳到之后一根木头(一根根跳，中间不能略过)，一次最多只能往上跳X高度或者往
下跳X高度。问怎么修改木头的高度（可以垫高可以砍掉一些变低）问能够让一个人从
起点跳到终点所作的最小改动是多少。
ex: 三根木头，高度 24 30 28， X=2， 答案是4
觉得应该是用DP，但是中间的状态方程就是没有想明白，请指教，或者是不是我的思路
就是错的，不是用DP？ | g***s
发帖数: 3811 | 2 DP is correct assumed all heights and X are integer．
【在 r******y 的大作中提到】
: 题目的意思是这样，就是有N根木头， 知道每跟木头的高度，然后一个人站在第一根木
: 头要跳到之后一根木头(一根根跳，中间不能略过)，一次最多只能往上跳X高度或者往
: 下跳X高度。问怎么修改木头的高度（可以垫高可以砍掉一些变低）问能够让一个人从
: 起点跳到终点所作的最小改动是多少。
: ex: 三根木头，高度 24 30 28， X=2， 答案是4
: 觉得应该是用DP，但是中间的状态方程就是没有想明白，请指教，或者是不是我的思路
: 就是错的，不是用DP？
| r******y
发帖数: 780 | 3 恩，都是integer
能具体说说那个状态转移方程吗？
还是有点晕，关键可能也没想明白到底那个状态应该怎么定义
谢谢了
【在 g***s 的大作中提到】
: DP is correct assumed all heights and X are integer．
| M*******a
发帖数: 1633 | | e********2
发帖数: 495 | 5 linear programming肯定可以做。
【在 r******y 的大作中提到】
: 题目的意思是这样，就是有N根木头， 知道每跟木头的高度，然后一个人站在第一根木
: 头要跳到之后一根木头(一根根跳，中间不能略过)，一次最多只能往上跳X高度或者往
: 下跳X高度。问怎么修改木头的高度（可以垫高可以砍掉一些变低）问能够让一个人从
: 起点跳到终点所作的最小改动是多少。
: ex: 三根木头，高度 24 30 28， X=2， 答案是4
: 觉得应该是用DP，但是中间的状态方程就是没有想明白，请指教，或者是不是我的思路
: 就是错的，不是用DP？
| e********2
发帖数: 495 | 6 min (|x1| + |x2| + ... + |xn|)
subject to:
x1+y1 < x2 + y2 + X
x2+y2 < x1 + y1 + X
准确的来说是个L1优化问题。有sparse解。
【在 e********2 的大作中提到】
: linear programming肯定可以做。
| l**********1
发帖数: 415 | 7 觉得从后往前用贪婪算法就是解了，还没想到反例。就大牛解答 | e********2
发帖数: 495 | 8 或者pseudopolynomial time：
两条ymax和ymin把这些点全包围，然后对夹在两条线之间的点做DP。
【在 r******y 的大作中提到】
: 恩，都是integer
: 能具体说说那个状态转移方程吗？
: 还是有点晕，关键可能也没想明白到底那个状态应该怎么定义
: 谢谢了
| z******g
发帖数: 271 | | g***s
发帖数: 3811 | 10 比较直观的做法：
M=max(a[i])
f(n)= min { g(n, i) + |a[n] - i| } i=0..M
g(n,m)=min { g(n-1, [m-X,m+X])}
O(N*M*X) or O(N*M*log(X))
g(n,m) ｎ个桩，最后一个的高度被调整成ｍ，所以只能从g(n-1,[m-X,m+X])过来。
【在 r******y 的大作中提到】
: 恩，都是integer
: 能具体说说那个状态转移方程吗？
: 还是有点晕，关键可能也没想明白到底那个状态应该怎么定义
: 谢谢了
| M*******a
发帖数: 1633 | 11 有道理，所以我想到个O(n)办法
就是一开始以第一根木头为准，后面的木头都根据前一根木头来greedy调整，记录所有
上升和下降的调整数量，比如
x=2
(2,6,2,6,9,9,6,7,4)
->
(2，4，2，4，6，8，6，7，5)
这样调整的值是
(0,-2,0,-2,-3,-1,0,0,1)
这样负数太多，所以(负数+正数)/木头数，再取反 = 1，第一棵树设置为2+1=3，再重
新调整为
(3,5,3,5,7,9,7,7,5)
这样调整的值是
(1,-1,1,-1,-2,1,0,1)
但是仍然好像不是最优解
【在 z******g 的大作中提到】
: 有点像leetcode candy
| g***s
发帖数: 3811 | 12 try {0,100,100,100,100,100,100}
X=2
【在 M*******a 的大作中提到】
: 有道理，所以我想到个O(n)办法
: 就是一开始以第一根木头为准，后面的木头都根据前一根木头来greedy调整，记录所有
: 上升和下降的调整数量，比如
: x=2
: (2,6,2,6,9,9,6,7,4)
: ->
: (2，4，2，4，6，8，6，7，5)
: 这样调整的值是
: (0,-2,0,-2,-3,-1,0,0,1)
: 这样负数太多，所以(负数+正数)/木头数，再取反 = 1，第一棵树设置为2+1=3，再重
| M*******a
发帖数: 1633 | 13 这个好像是不行
我作法是不是最优解法
不知道怎么最优法
【在 g***s 的大作中提到】
: try {0,100,100,100,100,100,100}
: X=2
| l******6
发帖数: 340 | 14 F(n , h) = abs(h(n) - h) if n == nmax
F(n , h) = abs(h - h(n)) + min (F(n + 1 , h + x)) where x = -X to X , limit
to h + x is within hmin and hmax
hmin = min(all h) hmax = max (all h)
ret = min F(0 , h) |
|
