uva12170 轻松爬山

给一组数（高度）h1,h2,...,hn，要求修改h2~h(n-1)的值，使得h1,h2,...,hn中任意相邻两个数的差的绝对值不超过d。将某个hx从a修改到b的代价为|a-b|，求最小总代价。
n<=100 d<=1e9

基本思路是常规的动态规划，用dp[i][j]表示考虑前i个高度，并且第i个高度修改为j时的最小代价。但是这样j的范围太大，所以标准解答将dp的第二个维度离散化了。

可以证明这样的结论：在最优解中，任何一个高度都可以写成的形式，hx是h1~hn中的某个高度，k是（-2n,2n）之间的整数。

下面证明它。

假设上图是最优解中某个任意位置x以及它左右的一些高度。先说明一下这个图，每个方块的中心表示它的高度，方块边长为d，相邻方块均相连从而相邻高度差不超过d。

我们以x为中心向两边扩展所有只以1个点相连的其他高度，当出现相邻两个方块的公共部分是线段时就停下，也就是我们只考虑图中那些实线方块。

如果这一组方块中有任意一个处在自己原先的位置，那么x的位置显然符合结论。如果它们全部都不在自己原先的位置，那么我们可以把这个整体向上或向下移动微小距离而保证整体代价不增加，这个过程持续到其中任意一个方块移回原始位置或者虚线方块被纳入实线方块内。至此，结论的正确性显而易见。

如此状态数是O(n³)，但转移似乎也要n²，时间复杂度承受不起。可以在计算dp(i,Hj)时按照Hj（Hj是一系列离散值）从小到大的顺序来算，由于dp(i,Hj)=|h[i]-Hj|+min{dp(i-1,Hx)|Hx∈[Hj-d,Hj+d]}，所以相当于计算Hx在区间[Hj-d,Hj+d]上dp(i-1,Hx)的最小值，可以用滑动窗口+单调队列来处理，从而使转移复杂度变成平摊后O(1)。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define y second
#define x first
#define LL long long
#define INF 1e15
using namespace std;

const int maxn=100+5;
LL n,d,h[maxn],dp[maxn][2*maxn*maxn],f[2*maxn*maxn];
int fcnt;
pair<LL,int> q[2*maxn*maxn];

void solve(){
    fcnt=0;
    
    for(int i=0;i<n;i++)
        for(int k=-n+1;k<=n-1;k++)
            f[fcnt++]=h[i]+k*d;
    
    sort(f,f+fcnt);
    
    for(int j=0;j<fcnt;j++){
        dp[0][j]=INF;
    }
    
    int j0,je;
    for(int i=0;i<fcnt;i++){
        if(f[i]==h[0])j0=i;
        if(f[i]==h[n-1])je=i;
    }
    
    dp[0][j0]=0;
    
    for(int i=1;i<n;i++){
        int L=0,R=0;//[L,R)
        int ft=0,rr=0;//[ft,rr)
        for(int j=0;j<fcnt;j++){
            
            while(f[L]<f[j]-d){
                if(L==q[ft].y)ft++;
                L++;
            }
            while(R<fcnt&&f[R]<=f[j]+d){
                LL cur=dp[i-1][R];
                while(rr>ft&&cur<=q[rr-1].x)rr--;
                q[rr++]=make_pair(cur,R);
                R++;
            }
            
            if(q[ft].x!=INF){
                dp[i][j]=abs(f[j]-h[i])+q[ft].x;
            }else dp[i][j]=INF;
        }
    }
    
    if(dp[n-1][je]==INF)printf("impossible\n");
    else printf("%lld\n",dp[n-1][je]);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&n,&d);
        for(int i=0;i<n;i++)scanf("%lld",&h[i]);
        solve();
    }
}