UVA - 12170 Easy Climb（dp+离散化+单调队列优化）

传送门

---

首先看下简化版的问题分析，当$n=3$n=3时，只有$h_2$h2​是可以修改的，而且修改之后必须同时在$[h_1-d,h_1+d],[h_3-d,h_3+d]$[h1​−d,h1​+d],[h3​−d,h3​+d]之间，即$[max(h_1,h_3)-d,min(h_1,h_3)+d]$[max(h1​,h3​)−d,min(h1​,h3​)+d]。如果这个区间是空的那么无解；否则我们发现$h_2$h2​只有三种情况：不变；$max(h_1,h_3)-d$max(h1​,h3​)−d；$min(h_1,h_3)+d$min(h1​,h3​)+d。

然后扩展一下，假如$h_1$h1​和$h_n$hn​之间有若干个需要修改的数，因为每个被修改的数一定是从两边递推而来的，那么我们将中间的$n-2$n−2个数看成一个数$H$H，仔细考虑这个转移过程。所以如果无解，则有：

$max(h_1,h_n)-min(h_1,h_n)>d*(n-1)$max(h1​,hn​)−min(h1​,hn​)>d∗(n−1)

当然无解的判断方法还有另外一种，下面介绍。

然后我们也不难得到，每个数都可以写成$h_i+k*d,-n<k<n$hi​+k∗d,−n<k<n，这样我们发现每个数的转移有$O(n^2)$O(n2)种可能

状态转移

设$f(i,x)$f(i,x)表示当前将第$i$i个数修改为x且前面的数都已经修改的最大结果，那么状态转移过程为：

$f(i,x)=abs(h_i-x)+min(f(i-1,y)),x-d \leq y \leq x+d$f(i,x)=abs(hi​−x)+min(f(i−1,y)),x−d≤y≤x+d

优化

离散化：

dp的第二维表示数的大小，却达到了1e9，显然没办法开数组存，怎么办？离散化！因为$2*n^2$2∗n2个$x$x是固定的，那么我们可以预处理得到所有的$x$x，那么我们以下标作为dp的第二维。然后第一维也可以优化，因为每次转移之和前面一维有关，因此直接滚动数组即可。

单调队列：

因为满足$x-d \leq y \leq x+d$x−d≤y≤x+d的$f(i-1,y)$f(i−1,y)是$i-1$i−1阶段的一个长度为$2*d$2∗d的滑动窗口，之前应该也提到过，滑动窗口的最值问题可以使用单调队列优化。然后此问题还可以更简单，因为我们从小到大枚举的$x$x，然后因为$x$x是由负数到正数的变化，$min(f(i-1,y))$min(f(i−1,y))是递增的，观察上述转移方程，不难发现每一阶段的状态转移都是先递减后递增的，因此维护一个指针即可找到滑动窗口的最小值

边界处理和答案

当$i=0$i=0时，只有当$x==a[i]$x==a[i]时（这个值一定存在的），$f[0][i]$f[0][i]初始化为$0$0（$i$i是$x$x的下标），其余为$inf$inf

然后遍历所有的$x$x，如果最后的状态中$x==a[n]$x==a[n]时（这个值也一定存在），$f[n][i]$f[n][i]就是最后的答案

当然如果上面没有判断是否存在答案，这里可以判断$f[n][i]$f[n][i]是否为$inf$inf即可判断是否有解

代码

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

ll a[105],q[maxn];
ll f[2][maxn];
int n;
ll d;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%lld",&n,&d);
        for(int i=0;i<n;i++)
            scanf("%lld",&a[i]);
        if(max(a[0],a[n-1])-min(a[0],a[n-1])>d*(n-1)){
            puts("impossible");
            continue;
        }
        int m=0; //记录所有可能的x
        for(int i=0;i<n;i++)
            for(int j=1-n;j<n;j++)
                q[m++]=a[i]+d*j;
        sort(q,q+m);
        m=unique(q,q+m)-q;  //离散化数组消去相等的x
        for(int i=0;i<m;i++){ //边界处理
            f[0][i]=INF;
            if(a[0]==q[i]) f[0][i]=0; //只有刚好q[i]==a[0]时边界为0其余为INF
        }
        int now=0; //定义在这里是为了下面输出结果
        for(int i=1;i<n;i++){
            int k=0; //单调队列的指针
            for(int j=0;j<m;j++){
                while(k<m && q[k]<q[j]-d) k++; //找到区间[x-d,x+d]的第一个值
                while(k+1<m && q[k+1]<=q[j]+d && f[now][k+1]<=f[now][k]) k++; //找到上个状态符合条件的最小值下标
                //处理两种转移情况
                if(f[now][k]==INF) f[now^1][j]=INF;
                else f[now^1][j]=f[now][k]+abs(q[j]-a[i]);
            }
            now^=1;
        }
        ll ans;
        for(int i=0;i<m;i++)
            if(q[i]==a[n-1]){
                ans=f[now][i];
                break;
            }
        printf("%lld\n",ans);
    }
    return 0;
}