题意

给一个有初始值的数组，并且其中每个位置单独限定最大值。

每次操作可以给任意一个位置在[0~最大值]的范围内加一减一

问在不超过k次操作后，相邻项的差的平方的最大值，最小为多少

算法

动态规划（TLE）

首先，虽然题目求的是相邻项差的平方的最大值的最小值。实际上绝对值越大平方越大，所以我们可以改为求相邻项绝对值的最大值的最小值。

根据题意，我们设计动态规划状态$dp\left[下标\right]\left[下标对应的值\right]\left[当前最大的差\right]=最少的操作次数dp[下标][下标对应的值][当前最大的差]\; =\; 最少的操作次数$dp[下标][下标对应的值][当前最大的差]=最少的操作次数

那么有状态转移

$dp\left[idx\right]\left[v_{new}\right]\left[max\right(d_{old},\mid v-v_{old}\mid \left)\right]=min\left(dp\right[idx-1\left]\right[v_{old}\left]\right[d_{old}]+\mid v_{new}-a[idx\left]\mid \right)dp[idx][v\_\{new\}][max(d\_\{old\},|v-v\_\{old\}|)]\; =\; min(dp[idx-1][v\_\{old\}][d\_\{old\}]+|v\_\{new\}-a[idx]|)$dp[idx][vnew​][max(dold​,∣v−vold​∣)]=min(dp[idx−1][vold​][dold​]+∣vnew​−a[idx]∣)

也就是我们对上一个的状态$v_{old},d_{old}v\_\{old\},d\_\{old\}$vold​,dold​，枚举下一个的值$v_{new}v\_\{new\}$vnew​，进行状态转移。

最后答案即是能让 $dp\left[n\right]\left[v\right]\left[d\right]\le kdp[n][v][d]\; \backslash leq\; k$dp[n][v][d]≤k成立的最小的d

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 取球放球
     * @param n int整型 箱子个数
     * @param k int整型 最多操作次数
     * @param a int整型vector 箱子内的球的个数
     * @param w int整型vector 箱子容量
     * @return int整型
     */
    int solve(int n, int k, vector<int>& a, vector<int>& w) {
        const int INF = 0x3f3f3f3f;
        // [idx][idx value][max diff] = min(k);
        vector<vector<vector<int>> > dp(2,vector<vector<int>>(501,vector<int>(501,INF)));
        for(int v = 0;v<=w[0];v++){
            dp[0][v][0] = abs(v-a[0]); // 第一个位置为v,最大差为0,的最小操作次数
        }
        for(int i =1;i<n;i++){ // 遍历下标
            // 清空状态
            for(int v= 0;v<=500;v++){
                for(int d = 0;d<=500;d++){
                    dp[i%2][v][d] = INF;
                }
            }
            for(int v = 0;v <= w[i];v++){ // 枚举当前位置上的值
                for(int ov = 0; ov <= w[i-1];ov++){ // 枚举前一个位置上的值
                    for(int d = 0;d<=500;d++){ // 枚举前一个状态的最大差值
                        dp[i%2][v][max(d,abs(v-ov))] = min(
                            dp[i%2][v][max(d,abs(v-ov))],
                            abs(v-a[i]) + dp[(i-1)%2][ov][d] // 状态转移
                        );
                    }
                }
            }
        }
        int ans = INF;
        for(int v = 0;v<=w[n-1];v++){ // 枚举最后一个的值
            for(int d = 0; d<=500;d++){ // 枚举所有差值
                if(dp[(n-1)%2][v][d] <= k){
                    ans = min(d,ans);
                }
            }
        }
        return ans*ans;
    }
};

复杂度分析

空间复杂度: 空间复杂度和我们的状态相关，其中下标使用了滚动数组，因此复杂度为 $O\left(max\right(w_i{)}^2)O(max(w\_i)^2)$O(max(wi​)2)

时间复杂度: 我们在操作上，遍历了每一个位置，每个状态向下一个状态转移会枚举所有下一个位置的可能取值，因此时间复杂度$=下标\cdot 状态\cdot 转移代价=下标\backslash cdot\; 状态\; \backslash cdot\; 转移代价$=下标⋅状态⋅转移代价 即是$O(n\cdot max(w_i{)}^3)O(n\; \backslash cdot\; max(w\_i)^3)$O(n⋅max(wi​)3)

动态规划，前缀和

注意到上面我们的状态已经满足空间复杂度，而在这种状态设计下，下标是不可少的，能减少的时间复杂度只可能是转移代价。

观察转移方程

$dp\left[idx\right]\left[v_{new}\right]\left[max\right(d_{old},\mid v-v_{old}\mid \left)\right]=\mid v_{new}-a\left[idx\right]\mid +min\left(dp\right[idx-1\left]\right[v_{old}\left]\right[d_{old}\left]\right)dp[idx][v\_\{new\}][max(d\_\{old\},|v-v\_\{old\}|)]\; =\; |v\_\{new\}-a[idx]|\; +\; min(dp[idx-1][v\_\{old\}][d\_\{old\}])$dp[idx][vnew​][max(dold​,∣v−vold​∣)]=∣vnew​−a[idx]∣+min(dp[idx−1][vold​][dold​])

总的来说状态关系里有4个值$v_{old},v_{new},d_{old},d_{new}v\_\{old\},v\_\{new\},d\_\{old\},d\_\{new\}$vold​,vnew​,dold​,dnew​

上一个方案中枚举了$v_{new}v\_\{new\}$vnew​,而$d_{new}d\_\{new\}$dnew​是推出的,所以转移代价为$O\left(max\right(w_i\left)\right)O(max(w\_i))$O(max(wi​))

如果我们能够 使用另外两个作为给定的，剩余的靠可优化的枚举或推出得到，也许就能优化转移代价。

先看上一个方案,我们以样例数据中头两个为例，[12,4],假设我们在处理第二个的时候进行到了 $v_{old}=4,d_{old}=8v\_\{old\}=4,d\_\{old\}\; =\; 8$vold​=4,dold​=8时，这时去枚举$v_{new}v\_\{new\}$vnew​有

因为$d_{new}=max(d_{old},\mid v_{new}-v_{old}\mid )d\_\{new\}\; =\; max(d\_\{old\},|v\_\{new\}-v\_\{old\}|)$dnew​=max(dold​,∣vnew​−vold​∣)

反过来就是 $d_{new}\ge d_{old},d_{new}\ge \mid v_{new}-v_{old}\mid )d\_\{new\}\; \backslash ge\; d\_\{old\},\; d\_\{new\}\; \backslash ge\; |v\_\{new\}-v\_\{old\}|)$dnew​≥dold​,dnew​≥∣vnew​−vold​∣)，但反过来以后上述等式变成不等式$d_{new}\ge max(d_{old},\mid v_{new}-v_{old}\mid )d\_\{new\}\; \backslash ge\; max(d\_\{old\},|v\_\{new\}-v\_\{old\}|)$dnew​≥max(dold​,∣vnew​−vold​∣)

状态的意义也改变了，从$dp\left[下标\right]\left[下标对应的值\right]\left[当前最大的差\right]=最少的操作次数dp[下标][下标对应的值][当前最大的差]\; =\; 最少的操作次数$dp[下标][下标对应的值][当前最大的差]=最少的操作次数变为$dp\left[下标\right]\left[下标对应的值\right]\left[最大差不大于的值\right]=最少的操作次数dp[下标][下标对应的值][最大差不大于的值]\; =\; 最少的操作次数$dp[下标][下标对应的值][最大差不大于的值]=最少的操作次数

状态转移变为$dp\left[i\right]\left[v\right]\left[d\right]=\mid v-a\left[i\right]\mid +min\left(dp\right[i-1\left]\right[max(0,v-d)\cdots min(w_{i-1},v+d)\left]\right[0\cdots d\left]\right)dp[i][v][d]\; =\; |v-a[i]|\; +\; min(dp[i-1][max(0,v-d)\; \backslash cdots\; min(w\_\{i-1\},v+d)][0\; \backslash cdots\; d])$dp[i][v][d]=∣v−a[i]∣+min(dp[i−1][max(0,v−d)⋯min(wi−1​,v+d)][0⋯d])

也就是如果我们给定$v_{new}=4,d_{new}=8v\_\{new\}=4,\; d\_\{new\}=8$vnew​=4,dnew​=8, 去考虑$v_{old}v\_\{old\}$vold​ 和 $d_{old}d\_\{old\}$dold​

注意到状态是个二维数组，且正好取的是数组中一个矩形区域中的最小值。

其中$dd$d是从零开始，我们可以考虑使用前缀和。

而对于$v_{old}v\_\{old\}$vold​ 我们可以采取set 增删或优选队列+访问记录增删

代码

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 取球放球
     * @param n int整型 箱子个数
     * @param k int整型 最多操作次数
     * @param a int整型vector 箱子内的球的个数
     * @param w int整型vector 箱子容量
     * @return int整型
     */
    int solve(int n, int k, vector<int>& a, vector<int>& w) {
      int maxd = 0;
      for(int i = 1;i<a.size();i++){
        maxd = max(maxd,abs(a[i]-a[i-1])); 
      }
      const int INF = 0x3f3f3f3f;
      // [idx][idx value][max diff] = min(k);
      vector<vector<vector<int>>> dp(2,vector<vector<int>>(501,vector<int>(maxd+1,INF)));
      for(int v= 0;v<=w[0];v++){
        for(int d = 0;d<=maxd;d++){
          dp[0%2][v][d] = abs(v-a[0]); // 第一个位置为v,最大差为0,的最小操作次数
        }
      }
      for(int i = 1;i<n;i++){
        for(int d = 0;d<=maxd;d++){
          // 方程 dp[i][v][d] = abs(v-a[i]) + min(dp[i-1][v-d ~ v+d][0~d])
          // 所以先搜d,且按照前缀最小值合并
          // 对v的搜索,其实是求滑动窗口里的最小值,所以一个维护区间中下标单增且值单增的数组
          deque<pair<int,int> > mink = {};
          for(int v = 0;v <= min(w[i-1],d);v++){ // 当前dp[i][0][d] 所覆盖的区间是[-d~d],只统计其中合法的部分
            while(mink.size() && dp[(i-1)&1][v][d] <= mink[mink.size()-1].first){ // 新增的元素应该大于最后一个元素
              mink.pop_back();
            }
            mink.push_back({dp[(i-1)&1][v][d],v});
          }
          for(int v = 0;v <= w[i];v++){
            int pos = max(0,v-d)-1;
            if(mink.size() && pos == mink[0].second) { // 移动区间窗口,删除区间最左
              mink.pop_front();
            }
            if(v+d <= w[i-1]){ // 移动区间窗口,加入区间最右
              while(mink.size() && dp[(i-1)&1][v+d][d] <= mink[mink.size()-1].first){ // 新增的元素应该大于最后一个元素
                mink.pop_back();
              }
              mink.push_back({dp[(i-1)&1][v+d][d],v+d});
            }
            dp[i&1][v][d] = mink.size() > 0 ? mink[0].first+abs(v-a[i]):INF; // 当前区间的最小值
          }
        }
        //  前缀最小值 0~d
        for(int v=0;v <= w[i];v++){
          for(int d = 1;d<=maxd;d++){
            dp[i&1][v][d] = min(dp[i&1][v][d],dp[i&1][v][d-1]);
          }
        }
      }

      int ans = INF;
      for(int v = 0;v<=w[n-1];v++){ // 枚举最后一个的值
        for(int d = 0; d<=maxd;d++){ // 枚举最大差值
          if(dp[(n-1)&1][v][d] <= k){
            ans = min(d,ans);
          }
        }
      }
      return ans*ans;
    }
};

复杂度分析

空间复杂度: 空间复杂度和我们的状态相关，其中下标使用了滚动数组，因此复杂度为 $O\left(max\right(w_i{)}^2)O(max(w\_i)^2)$O(max(wi​)2)

时间复杂度: 我们在操作上, 不再又已有状态去推下一个状态，而是由目标状态反过来在已有状态中查询，好处是查询的正好是二维数组中的一块矩形，这块矩形一个方向可以前缀和，另一个方向用队列优化到均摊$O\left(1\right)O(1)$O(1)的效率(每个位置至多一次增一次删)，也就是均摊的转义代价为常数，所以总时间复杂度为$O(n\cdot max(w_i{)}^2)O(n\; \backslash cdot\; max(w\_i)^2)$O(n⋅max(wi​)2)。