成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode] Minimum Adjustment Cost [Undone]

Aomine / 2826人閱讀

Problem

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 is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

Notice

You can assume each number in the array is a positive integer and not greater than 100.

Example

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.

Note Solution 
public class Solution {
    public int MinAdjustmentCost(ArrayList A, int target) {
        int n = A.size(), res = Integer.MAX_VALUE, max = res;
        int[][] dp = new int[n][101];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 100; j++) {
                dp[i][j] = i == 0 ? Math.abs(j - A.get(i)) : max;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= 100; j++) {
                for (int k = j-target; k <= j+target && k <= 100; k++) {
                    if (k >= 0 && dp[i-1][k] < max) dp[i][j] = Math.min(dp[i][j], dp[i-1][k]+Math.abs(j-A.get(i)));
                }
            }
        }
        for (int j = 0; j <= 100; j++) {
            res = Math.min(res, dp[n-1][j]);
        }
        return res;
    }
}



    public int MinAdjustmentCost(ArrayList A, int target) {  
        int n = A.size();  
        int max = 0;  
        for (int i = 0; i < n; i++) {  
            max = Math.max(max, A.get(i));  
        }  
        int[][] d = new int[n][max+1];  
        for (int j = 0; j <= max; j++) {  
            d[0][j] = Math.abs(A.get(0) - j);  
        }  
        int curMin = 0;  
        for (int i = 1; i < n; i++) {  
            curMin = Integer.MAX_VALUE;  
            for (int j = 0; j <= max; j++) {  
                d[i][j] = Integer.MAX_VALUE;  
                for (int k = Math.max(0, j-target); k <= Math.min(max, j+target); k++) {  
                    d[i][j] = Math.min(d[i][j], d[i-1][k] + Math.abs(A.get(i)-j));  
                    curMin = Math.min(curMin, d[i][j]);  
                }  
            }  
        }  
        return curMin;  
    }  
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65797.html

相關(guān)文章

  • [LintCode/LeetCode] Paint House I & Paint Hous

    摘要：在原數(shù)組上動規(guī)，每一行對應一個房子，每一個元素代表從第一行的房子到這一行的房子選擇這一種顏色所花的最小開銷。所以每個元素該元素的值上一行兩個與該元素不同列元素的值的較小者。不過這次要記錄三個變量本行最小值，本行第二小值，本行最小值下標。 Paint House Problem There are a row of n houses, each house can be painted ...

    ChristmasBoy 評論0 收藏0

  • [LintCode/LeetCode] Gas Station

    摘要：看到這個題目，怎樣可以不把它當成一個環(huán)路來分析，以及減少多余的空間呢例如，我們引入單次剩余油量，剩余油量和，總剩余油量和，以及可行起點四個參數(shù)。大體上說，只要，一定有解。所以跳過這個耗油量很大的油站，然后將下一個油站作為起點繼續(xù)判斷即可。 Problem There are N gas stations along a circular route, where the amount ...

    hedge_hog 評論0 收藏0

  • [LintCode] Minimum Absolute Difference in BST

    Problem Minimum Absolute Difference in BSTGiven a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes. Example Input: 1 3 ...

    curlyCheng 評論0 收藏0

  • [LintCode/LeetCode] Minimum Window Substring

    Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

    Corwien 評論0 收藏0

  • [LintCode/LeetCode] Find Minimum in Rotated Sorted

    摘要：排序數(shù)組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點和中點元素的大小關(guān)系即可。這里有一種情況是上述后三個，中點值和末位相等。此時，兩邊同時遞歸，并返回兩邊遞歸值的較小值。當首位和末位重合，說明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

    cgh1999520 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<