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

· · 题解

这题我不会做

在学习了几篇大佬的题解后，终于 AC 了这道题，来发篇题解记录一下。

题目传送门

题意简述

给定一个数列，你可以花费 1 代价将数列内的元素 +1 或 -1，首项和末项不能被改变，求让数列相邻两数差的绝对值小于等于 d 的最小代价。

分析

我们可以认为很多次的对单个元素的操作可以合并成对一个区间的操作。

首先我们先考虑无解的情况：

|a_1 - a_n| > d \times (n - 1)

证明：这是显然的吧。

然后我们考虑先构造一组解，使得可以剔除掉减少数列元素大小的这个操作。

于是我们可以构造数组 b，其中 b_1 = a_1，b_i = b_{i - 1} - d。（这里先假设我们可以改变终点的代价）

我们可以发现这样构造之后的 b_n \le a_n。我们可以通过若干次调整使得 b_n = a_n。

先来思考怎么处理操作区间。

引理：若干次区间操作都可以转化成对 b 的一个后缀进行操作。

证明：如果我们在区间 [l, r] \ (1 < l \le r < n) 中增加了 h 个单位，那么我们一定也会在 b_{r + 1} 中增加了 h 个单位，因为我们构造的 b 数组已经保证了前面一个元素是卡在后面一个元素的上界了，依次类推，我们发现若区间 [l, r] 增加了 h 则区间 [l, n] 也必定增加了 h。

然后来思考每次增加的高度 h：

将区间 [l, n] 上升高度 h 后会出现两种情况 b_i + h < a_i 和 b_i + h \ge a_i。我们很难计算这个代价，所以我们把 h 设置成 \min(a_i - b_i)，这样就不会出现上述的 b_i + h \ge a_i 的情况了，然后我们设 s_1 为满足 b_i < a_i 的位置数，s_2 为满足 b_i \ge a_i 的位置数，所以每当进行一次操作那么花费的金币数就会减少 s_1 \times h，增加 s_2 \times h。

所以我们可以直接贪心的想令 s_1 - s_2 越大越好。

证明：设 i 为当前 f(i) = s_1 - s_2 最大的可行后缀起点，设某最优解的第一步选了起点 l。

1：若 l < i，则有多出部分 f \le 0，则拆成先抬 i 后抬多出部分，代价不变。

2：若 l > i，则有多出部分 f \ge 0，改成先抬 i，代价不增。

综上，贪心策略正确。

代码


#include<bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define LLINF 0x3f3f3f3f3f3f3f3fLL
#define ft first
#define sd second
using ci=const int;
using ll=long long;
using ld=double;
using ull=unsigned long long;
using lli=__int128;
int T;
ll n,d;
ll a[5005];
ll b[5005];
signed main()
{
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    ll i,j;
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n>>d;
        for(i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        if(labs(a[1]-a[n])>(ll)d*(n-1)) 
        {
            cout<<"impossible\n";
            continue;
        }
        b[1]=a[1];
        for(i=2;i<=n;i++)
        {
            b[i]=b[i-1]-d;
        }
        while(b[n]!=a[n])
        {
            ll c=LLINF,ms=-LLINF,h,id,s=0;
            for(i=n;i>1;i--)
            {
                if(b[i]<a[i]) s++,c=min(c,a[i]-b[i]);
                else s--;
                if(b[i]!=b[i-1]+d&&s>ms)
                {
                    id=i;
                    h=c;
                    ms=s;
                }
            }
            h=min(h,b[id-1]-b[id]+d);
            for(i=id;i<=n;i++) b[i]+=h;
        }
        ll ans=0;
        for(i=1;i<=n;i++)
        {
            ans+=labs(a[i]-b[i]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}