取球放球_牛客博客

普通解法

考虑动态规划

用 $dp(i,j,k)$ 表示考虑前 $i$ 个数字,操作 $j$ 次，最后一个数字是 $k$ 的情况下相邻项的差的平方的最大值的最小值.

有了这个定义之后，转移就比较显然了：

$dp(i,j,k)$ 可以转移 $dp（i+1,x,y)$ 其中 $x$ 和 $y$ 取决于对位置 $i+1$ 的操作。

int solve(int n, int k, vector<int> a, vector<int> w){
    static int dp[105][505][505];
    assert(k < 505);
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][a[0]] = 0;
    for(int i = 0; i <= w[0]; ++i) {
        int t = abs(a[0]-i); dp[0][t][i] = 0;
    }
    for(int i = 0; i < n-1; ++i){
        for(int j = 0; j <= k; ++j){
            for(int x = 0; x <= w[i]; ++x){
                for(int y = 0; y <= w[i+1]; ++y){
                    int add = abs(a[i+1]-y);
                    if(j+add > k) continue;
                    dp[i+1][j+add][y] = min(dp[i+1][j+add][y], max(dp[i][j][x], abs(y-x)));
                }
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for(int i = 0; i <= k; ++i) {
        for(int x = 0; x <= w[n-1]; ++x) ans = min(ans, dp[n-1][i][x]);
    }
    return ans*ans;
}

$dp$ 数组的三维分别取决于 $n,k,和w$ 所以空间复杂度 $O(n*k*w)$

因为转移的过程中要枚举下一个数字是什么，所以单次转移是 $O(w)$ 的，总的时间复杂度 $O(n*k*w^2)$
当然，这样的复杂度并不能通过此题

最优解法

我们需要最小化最大值，所以可以去考虑二分答案。

二分检查相邻项的绝对值全部小于等于mid是否可行。

用动态规划去检查：

$dp(i,j)$ 表示考虑前 $i$ 个箱子，第 $i$ 个箱子的球的个数为 $j$ 并且 $[1,i]$ 的相邻箱子差的绝对值都不超过 $mid$ 最少需要几次操作，那么枚举第 $i+1$ 个箱子的球的个数去转移。第 $i+1$ 个箱子最少有 $max(0,j-mid)$ 个球，最多有 $min(w_{i+1},j+mid)$ 个球。

$dp[n][0...w_n]$ 中的最小值就是让所有相邻箱子中的球数差的绝对值不超过mid的最小操作次数。

根据最小操作次数和 $k$ 的关系来改变二分界限。

使用了一个二维数组 $dp(i,j)$ 来辅助二分判断，空间复杂度 $O(n*w)$

需要进行 $log(w)$ 次二分检查，动态规划部分时间复杂度为 $O(n*w^2)$ ,总的时间复杂度 $O(n*w^2*log(w))$

int solve(int n, int k, vector<int> a, vector<int> w){
    int l = 0, r = 500;
    int ans;
    int dp[105][505];
    while(l <= r){
        int mid = (r+l)>>1;
        memset(dp, 0x3f, sizeof dp);
        for(int i = 0; i <= w[0]; ++i) dp[0][i] = abs(a[0]-i);
        for(int i = 0; i < n-1; ++i){
            for(int x = 0; x <= w[i]; ++x){
                int down = max(0, x-mid);
                int up = min(w[i+1], x+mid);
                for(int y = down; y <= up; ++y)
                    dp[i+1][y] = min(dp[i+1][y], dp[i][x]+abs(a[i+1]-y));
            }
        }
        int mi = dp[n-1][0];
        for(int i = 1; i <= w[n-1]; ++i) mi = min(mi, dp[n-1][i]);

        if(mi <= k) ans = mid, r = mid-1;
        else l = mid+1;
    }
    return ans*ans;
}