l******2
发帖数: 41 | 1 Given an integer array, adjust each integers so that the difference of every
adjcent integers are not greater than a given number target.
If the array before adjustment is A, the array after adjustment is B, you
should minimize the sum of |A[i]-B[i]|
You can assume each number in the array is a positive integer and not
greater than 100
Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the
adjustment cost is 2 and it's minimal. Return 2. | r****7
发帖数: 2282 | 2 这个不就动态规划么，O(n)的复杂度
every
【在 l******2 的大作中提到】
: Given an integer array, adjust each integers so that the difference of every
: adjcent integers are not greater than a given number target.
: If the array before adjustment is A, the array after adjustment is B, you
: should minimize the sum of |A[i]-B[i]|
: You can assume each number in the array is a positive integer and not
: greater than 100
: Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the
: adjustment cost is 2 and it's minimal. Return 2.
| i*********e
发帖数: 21 | 3 element value需要在合理范围内，否则没法dp。
楼主应该漏了这点。 | m***l
发帖数: 1 | 4 "You can assume each number in the array is a positive integer and not
greater than 100 "
所以可以DP.
另一个方法是. 表明这个问题可以写成min-cost flow. 然后这个图很特别, 是series-
parallel graph.
然后表明用Booth&Tarjan的算法O(n log n)的时间即可. | t******5
发帖数: 30 | 5 能具体说说算法么，谢谢
【在 r****7 的大作中提到】
: 这个不就动态规划么，O(n)的复杂度
:
: every
| b*********e
发帖数: 26 | 6 int f[n][100]
第一维是数组里的数，第二维是那个数的取值，f[i][j]是第i个数取j(0
的cost
转移方程很恶心如果k很大的话
如果k==1的话
f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i-1][j+1])+ |A[i]-j|
最后输出f[N-1][]里最小的元素即可
【在 t******5 的大作中提到】
: 能具体说说算法么，谢谢
| b*********e
发帖数: 26 | 7 直接求max(A)和min(A)就好了吧
【在 i*********e 的大作中提到】
: element value需要在合理范围内，否则没法dp。
: 楼主应该漏了这点。
|
|
