485交了半年多了还在NBC，正常吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

485交了半年多了还在NBC，正常吗？

485交了半年多了还在NBC，正常吗？# EB23 - 劳工卡

r*y2018-11-21 08:11

1 楼

题目的意思是这样，就是有N根木头，知道每跟木头的高度，然后一个人站在第一根木
头要跳到之后一根木头(一根根跳，中间不能略过)，一次最多只能往上跳X高度或者往
下跳X高度。问怎么修改木头的高度（可以垫高可以砍掉一些变低）问能够让一个人从
起点跳到终点所作的最小改动是多少。
ex: 三根木头，高度 24 30 28， X=2，答案是4
觉得应该是用DP，但是中间的状态方程就是没有想明白，请指教，或者是不是我的思路
就是错的，不是用DP？

x*o2018-11-21 08:11

2 楼

找了几个Emma都是这么说，估计就是在NBC了。难道不是应该转到local office 吗？指
纹7月就弄了，然后就石沉大海了

g*s2018-11-21 08:11

3 楼

DP is correct assumed　all heights and X are integer．

【在 r******y 的大作中提到】

: 题目的意思是这样，就是有N根木头，知道每跟木头的高度，然后一个人站在第一根木
: 头要跳到之后一根木头(一根根跳，中间不能略过)，一次最多只能往上跳X高度或者往
: 下跳X高度。问怎么修改木头的高度（可以垫高可以砍掉一些变低）问能够让一个人从
: 起点跳到终点所作的最小改动是多少。
: ex: 三根木头，高度 24 30 28， X=2，答案是4
: 觉得应该是用DP，但是中间的状态方程就是没有想明白，请指教，或者是不是我的思路
: 就是错的，不是用DP？

x*i2018-11-21 08:11

4 楼

same here....5月RD6月FP，到现在连combo卡都没有，同事6月RD绿卡都到手了。

r*y2018-11-21 08:11

5 楼

恩，都是integer
能具体说说那个状态转移方程吗？
还是有点晕，关键可能也没想明白到底那个状态应该怎么定义
谢谢了

【在 g***s 的大作中提到】

: DP is correct assumed　all heights and X are integer．

t*t2018-11-21 08:11

6 楼

这个... 同问一下

M*a2018-11-21 08:11

7 楼

不用DP把，二分法吧

e*22018-11-21 08:11

8 楼

linear programming肯定可以做。

【在 r******y 的大作中提到】

e*22018-11-21 08:11

9 楼

min (|x1| + |x2| + ... + |xn|)
subject to:
x1+y1 < x2 + y2 + X
x2+y2 < x1 + y1 + X
准确的来说是个L1优化问题。有sparse解。

【在 e********2 的大作中提到】

: linear programming肯定可以做。

l*12018-11-21 08:11

10 楼

觉得从后往前用贪婪算法就是解了，还没想到反例。就大牛解答

e*22018-11-21 08:11

11 楼

或者pseudopolynomial time：
两条ymax和ymin把这些点全包围，然后对夹在两条线之间的点做DP。

【在 r******y 的大作中提到】

: 恩，都是integer
: 能具体说说那个状态转移方程吗？
: 还是有点晕，关键可能也没想明白到底那个状态应该怎么定义
: 谢谢了

z*g2018-11-21 08:11

12 楼

有点像leetcode candy

g*s2018-11-21 08:11

13 楼

比较直观的做法：
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*a2018-11-21 08:11

14 楼

有道理，所以我想到个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*s2018-11-21 08:11

15 楼

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*a2018-11-21 08:11

16 楼

这个好像是不行
我作法是不是最优解法
不知道怎么最优法

【在 g***s 的大作中提到】

: try {0,100,100,100,100,100,100}
: X=2

l*62018-11-21 08:11

17 楼

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)