本文主要是介绍UVA 12170 Easy Climb(dp+单调队列优化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出一个序列，首尾不可改变，要求你使序列满足相邻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。
总结：前后关联的训练序列问题一般可以用区间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 heightsint 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之间的所有数就是修改时候可能用到的结果// dpint 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;
}
这篇关于UVA 12170 Easy Climb(dp+单调队列优化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
