Post Office

On one line there are n houses. Give you an array of integer means the the position of each house. Now you need to pick k position to build k post office, so that the sum distance of each house to the nearest post office is the smallest. Return the least possible sum of all distances between each village and its nearest post office.

一下解决方案优点：

• Dynamic Programming，dp[ki][ni]存的是ni+1个villiage简历ki个post office的最小cost
• 当在(left,right)中建立office的代价合理利用befor,after数组信息，是O(1),不是O(N)依次求和

参考 这里

class Solution {
public:
    /**
     * @param A an integer array
     * @param k an integer
     * @return an integer
     */
    int postOffice(vector<int>& A, int k) {
        // Write your code here

        sort(A.begin(),A.end());

        int n=A.size();
        before=vector<int>(n);
        after=vector<int>(n);

        for(int i=1;i<n;i++)
        {
            before[i]=before[i-1]+i*(A[i]-A[i-1]);
        }

        for(int i=n-2;i>=0;i--)
        {
            after[i]=after[i+1]+(n-1-i)*(A[i+1]-A[i]);
        }

        vector<vector<int>> dp(k,vector<int>(n));

        for(int ki=0;ki<k;ki++)
        {
            for(int ni=ki;ni<n;ni++)
            {
                if(ki==0)dp[ki][ni]=getCost(0,ni,A);
                else
                {
                    dp[ki][ni]=INT_MAX;
                    for(int nj=0;nj<ni;nj++)
                    {
                        //这里需要返回的是总共的和！！
                        dp[ki][ni]=min(dp[ki][ni],dp[ki-1][nj]+getCost(nj+1,ni,A));
                        //dp[ki][ni]=min(dp[ki][ni],max(dp[ki-1][nj],getCost(nj+1,ni,A)));
                    }
                }
            }
        }

        return dp.back().back();
    }

    vector<int> before,after;

    //如果在left,right建一个post office代价
     int getCost(int left, int right, vector<int>& A)
     {
         int mid = (left + right) >> 1;

         int leftCost = before[mid] - before[left] - left*(A[mid] - A[left]);
         int rightCost = after[mid] - after[right] - (A.size() - 1 - right)*(A[right] - A[mid]);
         return leftCost + rightCost;
     }
};