分析

老样子，先判断无解情况。

我们假设 \(h_n\) 无限高于或者低于 \(h_1\)，那么中间的那些都必须尽力去逼近 \(h_n\)，一定是递增或递减的。但由于相邻的两堆石头高度差不能超过 \(d\)，所以递增或递减的最大长度为 \((n-1) \cdot d\)。如果 \(|h_n-h_1| > (n-1) \cdot d\)，那么肯定是无解。反过来想，如果不大于，那么一定存在合法的构造方法，即一定有解。

手算以下不难发现，对于每一个 \(i\)，都有 \[ h_i' \in [\max{(h_{i-1},h_{i+1})-d,\min{(h_{i-1},h_{i+1})+d}}] \] 那么如果 \(h_i\) 不在区间内，将其变为距离它最近的区间边界是最优的，因为差值最小。

如果 \(h_i\) 在区间内，那么可以让它不变，这样贡献为 0。

如果这样去做了，那么对于每个 \(h_i '\)，都能写成 \(h_x+kd \quad (x \in [1,n],k \in [-n,n])\) 的形式。

感性证明一下，如果改变 \(h_i\) 的值，那么一定是在某个现有的 \(h_i\) 或 \(h_i'\) 的基础加上过减去 \(d\)；如果不改变，令 \(k=0\) 即成立。严格证明可以用归纳法，这里不再赘述。

所以所有可能的值的个数为 \(2n^2\)，记为 \(a\)。

设 \(f(i,j)\) 表示前 \(i\) 堆石头，第 \(i\) 堆的高度为 \(j\) 时，所需要的最小代价。

边界

\[ f(i,j) = \begin{cases} 0 & i=0,j=h_1 \\ \inf & \text{otherwise} \end{cases} \]

转移

\[ f(i,j) = \min \limits_{j-d \le k \le j+d} { \{ f(i-1,k)+ |a_i-j| \} } \]

\[ f(i,j) = \min_{j-d \le k \le j+d} { \{ f(i-1,k) \} } + |a_i - j| \]

滚动数组+单调队列优化即可。

最终答案 \[ ans= \max{\{ f(n-1,i) \}} \quad |h_n-i| \le d \]

由于 \(j\) 这一维值域过大，具体实现时可以离散化，这一维存下标。

状态数 \(n^2\) 个，决策 \(n\) 个，转移 \(O(1)\)，总复杂度 \(O(n^3)\)。

CODE

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N=105, M=N*N*2;
int t, n, m, d, h[N], q[M];
ll ans, a[M], f[2][M];
inline void init() {
    for(int i=1;i<=n;++i) {
        for(int j=-n;j<=n;++j) if(h[i]+j*d>=0) // 高度不会小于0
            a[++m]=h[i]+j*d;
    }
    sort(a+1,a+m+1);
    m=unique(a+1,a+m+1)-a-1;
    for(int i=1;i<=n;++i) h[i]=lower_bound(a+1,a+m+1,h[i])-a;
    // 离散化去重，现在和h[i]存的是原来h[i]在a中的位置。
}
inline void sol() {
    m=0, ans=1e15;
    memset(f,0x3f,sizeof(f));
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;++i) scanf("%d",&h[i]);
    if(abs(h[1]-h[n])>(n-1)*d) { puts("impossible"); return; }
    // 无解
    init();
    int p=1;
    f[0][h[1]]=0;
    for(int i=2;i<n;++i) {
        int k=0, l=1, r=0;
        for(int j=1;j<=m;++j) {
            while(l<=r&&a[q[l]]<a[j]-d) ++l;
            // 排除不合法（越界）的决策。
            while(k<=m&&a[k+1]<=a[j]+d) {
                ++k;
                while(l<=r&&f[p^1][q[r]]>=f[p^1][k]) --r;
                // 维护决策单调增
                q[++r]=k;
            }
            if(l<=r) f[p][j]=f[p^1][q[l]]+abs(a[h[i]]-a[j]);
            // 队头即使最优决策。
        }
        p^=1;
    }
    for(int i=1;i<=m;++i) if(abs(a[h[n]]-a[i])<=d)
        ans=min(ans,f[p^1][i]);
    printf("%lld\n",ans);
}
int main() { for(scanf("%d",&t);t--;sol()); }