Lintcode91 Minimum Adjustment Cost solution 题解

Nicole 2017-08-10
【题目描述】


Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment isA, the array after adjustment isB, you should minimize the sum of|A[i]-B[i]|

给一个整数数组,调整每个数的大小,使得相邻的两个数的差小于一个给定的整数target,调整每个数的代价为调整前后的差的绝对值,求调整代价之和最小是多少。

【注】:你可以假设数组中每个整数都是正整数,且小于等于100。

【题目链接】

www.lintcode.com/en/problem/minimum-adjustment-cost/

【题目解析】

这道题是背包问题。

mac[i][j]表示前i个元素满足要求且第i个元素为j的最小cost。

初始化:mac[1][j] = Math.abs(A[0] - j),根据题意j在1到100之间。

对于所有在范围内的k,当第i位元素取j时,取符合要求的第i-1位元素为k的情况的最小值,其中abs(j-k)的值要小于target才能符合要求。

如果第i-1个数是j, 那么第i-2个数只能在[lowerRange, UpperRange]之间,lowerRange=Math.max(0, j-target), upperRange=Math.min(99, j+target),

【参考答案】

www.jiuzhang.co...
【题目描述】


Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment isA, the array after adjustment isB, you should minimize the sum of|A[i]-B[i]|

给一个整数数组,调整每个数的大小,使得相邻的两个数的差小于一个给定的整数target,调整每个数的代价为调整前后的差的绝对值,求调整代价之和最小是多少。

【注】:你可以假设数组中每个整数都是正整数,且小于等于100。

【题目链接】

www.lintcode.com/en/problem/minimum-adjustment-cost/

【题目解析】

这道题是背包问题。

mac[i][j]表示前i个元素满足要求且第i个元素为j的最小cost。

初始化:mac[1][j] = Math.abs(A[0] - j),根据题意j在1到100之间。

对于所有在范围内的k,当第i位元素取j时,取符合要求的第i-1位元素为k的情况的最小值,其中abs(j-k)的值要小于target才能符合要求。

如果第i-1个数是j, 那么第i-2个数只能在[lowerRange, UpperRange]之间,lowerRange=Math.max(0, j-target), upperRange=Math.min(99, j+target),

【参考答案】

www.jiuzhang.com/solutions/minimum-adjustment-cost/
显示全文

查看更多主题的豆瓣日记和相册

Nicole
作者Nicole
12日记 0相册

全部回应 0 条

添加回应

Nicole的热门日记

值得一读

    豆瓣
    我们的精神角落
    免费下载 iOS / Android 版客户端
    App 内打开