天池 在线编程 放小球（动态规划）

n <= 100
W[i] <= 100

样例 1:
输入: 
5
6
[1,2,3,4,5]
[15,15,15,15,15]
说明
共有5个桶，最多操作6次，
桶内的小球分别是1,2,3,4,5，
桶的最大容量分别是15,15,15,15,15。

输出: 
0

class Solution {
public:
    /**
     * @param n: the number of buckets
     * @param k: the maximum times of operations
     * @param A: the number of balls in each bucket
     * @param W: the maximum capacity of each bucket
     * @return: return the minimum square value of the maximum difference
     */
    int getAns(int n, int k, vector<int> &A, vector<int> &W) {
        // write your code here
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k+1, vector<int>(101, INT_MAX)));
        for(int ki = 0; ki <= k; ++ki)
        {	// 初始化
            if(A[0]-ki >= 0)//减少球
                dp[0][ki][A[0]-ki] = 0;//边界
            if(A[0]+ki <= W[0])//增加球
                dp[0][ki][A[0]+ki] = 0;
        }
        for(int i = 1; i < n; ++i)
        {	//遍历样本
            for(int k1 = 0; k1 <= k; ++k1)
            {	//到前一个位置为止，共操作了 k1 次
                for(int w1 = 0; w1 <= W[i-1]; ++w1)
                {    //前一个位置 的重量 w1
                    if(dp[i-1][k1][w1] == INT_MAX)
                        continue;
                    for(int k2 = 0; k2+k1 <= k; ++k2)
                    {	// 当前位置的操作次数 k2, 总次数 k1+k2 不能超
                        if(A[i]-k2 >= 0)//拿走一些
                            dp[i][k2+k1][A[i]-k2] = min(dp[i][k2+k1][A[i]-k2], max(dp[i-1][k1][w1], (w1-A[i]+k2)*(w1-A[i]+k2)));
                        if(A[i]+k2 <= W[i])//放进去一些
                            dp[i][k2+k1][A[i]+k2] = min(dp[i][k2+k1][A[i]+k2], max(dp[i-1][k1][w1], (w1-A[i]-k2)*(w1-A[i]-k2)));
                    }
                }
            }
        }
        int ans = INT_MAX;
        for(int ki = 0; ki <= k; ++ki)
        {
            for(int wi = 0; wi <= W[n-1]; ++wi)
                ans = min(ans, dp[n-1][ki][wi]);
        }
        return ans;
    }
};