UVA 12170 Easy Climb(dp+单调队列优化)

向右看齐 2021-12-16 23:34 240阅读 0赞

## 题意：给出一个序列，首尾不可改变，要求你使序列满足相邻2个|x\_i - x\_(i-1)| <=d，改变的代价就是两数相减绝对值，问最小代价。 ##

## 分析： ##

## 区间dp类问题，根据题意，我们需要修改2到n-1之间的一些h的值，使得相邻2个h值差的绝对值不超过d。因为可以修改的数是一个实数，无法一一枚举，因此需要仔细对问题进行分析。 ##

## 首先，考虑只有3个值的情况：h1, h2, h3。那么根据题意，h2应该在区间\[h1-d,h1+d\]和\[h3-d,h3+d\]之间，即h1应该在\[max(h1,h3)-d,min(h1,h3)+d\]之间。如果这个区间是空集，即abs(h3-h1)>(3-1)\*d，那么自然无解，否则，如果h2就在区间内部，那么不需要修改；如果h2<max(h1,h3)-d，那么就修改为max(h1,h3)-d；如果h2>min(h1,h3)+d，那么就修改为min(h1,h3)+d。可以发现，在这个简单的问题中，h2的最优修改方案只有这3种情况。并且我们还发现了，如果要修改，一定是修改成形如hp+k\*d的形式。 ##

## 接下来我们考虑有n个值的情况，根据类似的推理可以得出：如果abs(hn-h1)>(n-1)\*d时候，一定无解。如果满足这个条件，那么中间的每个数字要么不变，要么变成形如hp+k\*d的形式。由于abs(hn-h1)<=(n-1)\*d。那么k的取值范围最大就是\[-n+1,n-1\]，一共有2n-1种情况，另外，p的取值范围是\[1,n\]，即hp+k\*d一共有O(n^2)种情况。设dp(i,x)表示已经修改了i-1个数，第i个数改成x时候还需要的最小费用。那么不难得到如下的状态转移方程： ##

## dp(i,x)=abs(hi-x)+min\{dp(i-1,y)|abs(x-y)<=d\}; ##

## 上述方程表示：当固定了i,x的时候，我们需要考察在区间\[x-d,x+d\]中的所有y值，并选出其中最小的那个dp值。这样，需要O(d)时间确定一个状态，而所有的状态一共有O(n^3)种，因此总的时间复杂度会高达O(N^4)。这时需要用单调队列来加以优化：先把区间\[x-d,x+d\]看做一个固定的区间，区间长度恒为2d，那么问题就转化为求在该区间内的最小值，如果我们从小到大枚举x，那么问题就转化为了求一个长度为2d的滑动区间的最小值，这正可以用单调队列加以解决，求出每个滑动窗口的最小值的平摊复杂度为O(1)，即我们最终只需要O(1)时间即可确定出最小值，那么总的时间复杂度降为O(N^3)，可以在时间限制内加以解决。 ##

## 最后说一点：虽然说是用单调队列来求每个滑动窗口的最小值，然而再深入分析一步就会发现一个规律，每次算完一个阶段后，该阶段的dp序列呈现的是一个先下降，后上升的趋势，而且下降时候的最低点一定是整个序列的最低点。（因为合法的区间中最中间的值费用是最小的，往左右走都会越来越偏离最优解，单调性为先减后增）这样，我们只需要一个front指针即可维护优先队列了。 ##

## 参考：[https://blog.csdn.net/u014800748/article/details/49024143][https_blog.csdn.net_u014800748_article_details_49024143]。 ##

## 总结：前后关联的训练序列问题一般可以用区间dp来解决，基本都是定义dp\[i\]\[j\]前i个数以j为结尾的...。这题细节很多，用到了很多技巧和方法，收获不少，很好的一道题，还得回过头来研究。 ##

## LRJ代码： ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int maxn = 100 + 5;
    const int maxx = maxn*maxn*2;
    const LL  INF = (1LL << 60);
    LL h[maxn], x[maxx], dp[2][maxx];
    
    int main () {
      int T;
      cin >> T;
      while(T--) {
        int n;
        LL d;
        cin >> n >> d;
        for(int i = 0; i < n; i++) cin >> h[i];
        if(abs(h[0] - h[n-1]) > (n-1)*d) {
          cout << "impossible\n";
          continue;
        }
        // useful heights
        int nx = 0;
        for(int i = 0; i < n; i++)
          for(int j = -n+1; j <= n-1; j++)
            x[nx++] = h[i] + j*d;// 把所有可能用到的修改结果都存放到x数组中
        sort(x, x+nx);
        nx = unique(x, x+nx) - x;//将x数组从小到大排序并去重，那么0...nx-1之间的所有数就是修改时候可能用到的结果
        // dp
        int t = 0;//因为只有奇，偶两种变化，且i只依赖于i-1时候的情况，因此可以用滚动数组优化
        for(int i = 0; i < nx; i++) {
          dp[0][i] = INF;
          if(x[i] == h[0]) dp[0][i] = 0;//初始化时候，只有恰好等于h0时候费用为0，其他均为INF
        }
        for(int i = 1; i < n; i++) {
          int k = 0;//单调队列的front指针
          for(int j = 0; j < nx; j++) {//从小到大枚举x值，因为所有需要用到的x值都在x数组中，因此等价于枚举下标
            while(k < nx && x[k] < x[j]-d) k++;//找到第一个符合条件的x[k]
            while(k+1 < nx && x[k+1] <= x[j]+d && dp[t][k+1] <= dp[t][k]) k++; //min in sliding window 第i处的x值为x[j]，如果不符合后者>前者，那么就出队列
            if(dp[t][k] == INF) dp[t^1][j] = INF; // (t, k) is not reachable 最小的那个dp[t][k]不存在，那么新的状态也不存在
            else dp[t^1][j] = dp[t][k] + abs(x[j] - h[i]); //得到x[j]处对应的最小值
          }
          t ^= 1;//更新为当前状态
        }
        for(int i = 0; i < nx; i++)
          if(x[i] == h[n-1]) cout << dp[t][i] << "\n";
      }
      return 0;
    }

[https_blog.csdn.net_u014800748_article_details_49024143]: https://blog.csdn.net/u014800748/article/details/49024143