P3202 [HNOI2009]通往城堡之路 神仙题

题目描述

听说公主被关押在城堡里，彭大侠下定决心：不管一路上有多少坎坷，不管城堡中的看守有多少厉害，不管救了公主之后公主会不会再被抓走，不管公主是否漂亮、是否会钟情于自己，他将义无反顾地朝着城堡前进。

可是，通往城堡的路上出现了一些情况。抽象地说，假象地图在二维平面的第一象限。在每个横轴的x位置上有一个高为hx的支撑点，如果彭大侠没有跳到支撑点上，那么他就会掉下去，牺牲在路途。

开始时彭大侠在起点（1，h1）处，而城堡的入口在（n，hn）处。彭大侠每次可以从支撑点（x，hx）跳到支撑点（x+1，hx+1）。但是彭大侠每次的跳跃能量只有d，也就是说，每次跳跃必须满足条件|hx+1-hn|<=d。换句话说，如果两个相邻支撑点的纵向落差大于d，那么彭大侠就无法跳跃了！幸运的是，彭大侠还有一个杀手锏。 在起点处，他可以花一个金币，把某个支撑点升高1个单位，或者降低1个单位。但是，起点处和城堡入口处的支撑点高度不能改变，并且一旦离开起点彭大侠就无法使用该杀手锏。

彭大侠被告知100个金币可兑换一单位生命。于是他希望通过少花金币来保存更多单位的生命。

他终于找到了你这位热心的高手，请你帮他规划一下以便耗费尽量少的金币来到达城堡。
输入输出格式
输入格式：

文件第一行包含一个整数m(m<=5)，表示问题求解次数。接下来的2m行依次表示每次求解的输入数据块。每个输入数据块占2行，其中第一行包含两个整数n和d，分别表示从起点到城堡入口处必须经过的支撑点数和每次跳跃允许的最大纵向落差，n和d之间用空格隔开，输入数据保证2<=n<=5000，0<=d<=109；第二行包含用空格隔开的n个非负整数h1、h2、...、hn，其中hi(1<=i<=n)表示第i个支撑点的高度，特别地，h1表示彭大侠出发时所在支撑点的高度，hn表示城堡入口所在支撑点的高度，输入数据保证对所有1<=i<=n有0<=hi<=109。

输出格式：

有m行，第I(1<=I<=m)行表示第I次求解时彭大侠到达城堡必须耗费的最少金币数量。若无论怎样使用杀手锏他都无法到达城堡，则输出impossible。输入数据保证答案在int64范围之内。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define duke(i,a,n) for(register int i = a;i <= n;++i)
#define lv(i,a,n) for(register int i = a;i >= n;--i)
#define clean(a) memset(a,0,sizeof(a))
const long long INF = 1LL << 50;
typedef long long ll;
typedef double db;
template <class T>
void read(T &x)
{
    char c;
    bool op = 0;
    while(c = getchar(), c < ‘0‘ || c > ‘9‘)
        if(c == ‘-‘) op = 1;
    x = c - ‘0‘;
    while(c = getchar(), c >= ‘0‘ && c <= ‘9‘)
        x = x * 10 + c - ‘0‘;
    if(op) x = -x;
}
template <class T>
void write(T x)
{
    if(x < 0) putchar(‘-‘), x = -x;
    if(x >= 10) write(x / 10);
    putchar(‘0‘ + x % 10);
}
const int N = 1e4;
int n,t;
ll d,a[N],b[N],ans = 0;
int main()
{
    read(t);
    while(t--)
    {
        read(n);read(d);
        ans = 0;
        duke(i,1,n)
        {
            read(a[i]);
        }
        b[1] = a[1];
        duke(i,2,n)
        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;
            lv(i,n,2)
            {
                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;
            }
        }
        duke(i,1,n)
        ans += abs(a[i] - b[i]);
        printf("%lld\n",ans);
    }
    return 0;
}