题解 P3202 【[HNOI2009]通往城堡之路】

· · 题解

【膜拜解决此题的远古神犇】

首先，我们构造出一组【可行解】，也就是以a[i]为初始高度，后面每一级都下降d个高度（此时不考虑a[n]不变的条件）

我们可以肯定，最终答案一定是在这个【（伪）解】基础上，让一些区间升高得到的

那么我们现在就要升高一些区间

（当前【可行解】用b数组来表示）

假定我们让一个区间升高h，并且满足b[i]+h<=a[i]，那么，假定这段区间有s1个点，b[i]<a[i]，s2个点，b[i]>=a[i]，则ans-=(s1*h);ans+=(s2*h)

也就是说，此时让这段区间升高h，答案会更优

那么我们每次寻找一段区间，使其加上这个h

当然，前提是满足这个区间的b[i]+h<=a[i]，也就是h=min（a[i]-b[i]）

【当然还有奇奇怪怪的小边界咯，这里并不会说，自己推一推吧！】

我们可以发现，b[n]这个点，一定是需要升高的，并且升高到a[n]之后就不能再升高

那么我们寻找一个后缀区间，则至少会增高b[n]这个节点

假设通过上述操作，现在b[n]已经等于a[n]，这个解法就是最优的

1.任何一段区间再增高，不会使答案更优

首先设该区间为[i,j]，既然该区间能够升高，那么则必有s1*h>s2*h--->s1>s2

假定[j+1,n]增加过，那么在枚举后缀时，是不会遗漏的，所以此时[i,j]不增高是不可能的

假定[j+1,n]没有增加过，那么，b[j]与b[j+1]的差值必定为d，一旦增加b[j]，则解必定不合法

2.任何一段区间再降低，不会使答案更优

设区间为[i,j]

假定[i,j]增高过，那么降低就相当于增高的反操作，也就是撤销增高---既然撤销更优，那么我们根本就不会增加它

假定[i,j]没有增高过，那么他们就必定不能降低---因为初始的b[i~j]已经是可行解的最低高度了

由此得证

代码

#define ll long long
#define inf 1LL<<50
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 5010
using namespace std;
int n,T;
ll d;
ll a[N],b[N];
ll ans;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%lld",&n,&d); 
        ans=0;
        for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
        b[1]=a[1];
        for(int i=2;i<=n;++i) b[i]=b[i-1]-d;
        if(abs(a[n]-a[1])>(ll)d*(n-1))
        {puts("impossible");continue;}
        while(b[n]!=a[n])
        {
            ll tm=-inf,at,add,val=inf,s=0;
            for(int i=n;i>1;--i)
            {
                if(b[i]<a[i]) s++,val=min(val,a[i]-b[i]);
                else s--;
                if(s>tm&&b[i]!=b[i-1]+d) tm=s,at=i,add=val;
            }
            add=min(add,b[at-1]+d-b[at]);
            for(int i=at;i<=n;++i) b[i]+=add;
        }
        for(int i=1;i<=n;++i) ans+=abs(a[i]-b[i]);
        printf("%lld\n",ans);
    }
    return 0;
}