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

太难了;

首先,它标了个Tarjan的标签;

然后,应该是有人用什么仙人掌+DP做的吧;

然而还是用的贪心;

根本不会;


就是把所有的==都先设为最差值==;

然后一点点的往上调;

然后就是贪心;

定义 :
low : 从n到现在i b[i]<=a[i] 的个数;

up : 从n到现在i b[i]>a[i] 的个数;

我们找一个 ==low-up 最大的后缀==;

先上调;

调的距离是 min ( a[i]-b[i] ) |a[i]>b[i];

因为这样我们 up 增加的值可以用 low 增加的值来==抵消==;

而且会有一部分 low 的值会使 ans 减小;

所以最优;

但是上调距离==有边界==, 即前一个 b[i-1]+d < b[i];

所以 b[i] 上调的最大距离要和 b[i-1]+d-b[i] 取 min;


    #include "iostream"
    #include "stdio.h"
    #include "algorithm"
    #define II int
    #define LO long long
    #define R register
    #define I 123456
    using namespace std;

    II t,n;

    LO d;

    LO a[I], b[I];

    LO gg(R LO x) { return x<0 ? -x : x ; }

    LO smaler(R LO a,R LO b) { return a<b ? a : b ; }

    int main()
    {
        scanf("%d",&t);
        while (t--) {
            scanf("%d%lld",&n,&d);
            for(R II i=1;i<=n;i++) scanf("%lld",&a[i]);

            if(gg(a[n]-a[1])>d*(n-1)) {
                printf("impossible\n");
                continue ;
            }

            b[1]=a[1];
            for(R II i=2;i<=n;i++) b[i]=b[i-1]-d; 

            while (b[n]!=a[n]) {
                R LO low=0,up=0,wei,oo=-1e18,op=1e18, ko=0;
                for(R II i=n;i>1;i--)
                {
                    a[i]>b[i] ? low++ : up++ ;     
                    if(a[i]>b[i]) {
                        op=smaler(op,a[i]-b[i]);
                    } 
                    if(low-up>=oo && b[i-1]+d!=b[i]) {
                        oo=low-up;
                        wei=i;
                        ko=op;
                    }
                }

                ko=smaler(ko,b[wei-1]+d-b[wei]);
                for(R II i=wei;i<=n;i++) b[i]+=ko;
            }

            R LO ans=0;
            for(R II i=1;i<=n;i++) ans+=gg(a[i]-b[i]);
            printf("%lld\n",ans); 
        }
        exit(0);
    }


发表于 2017-10-26 21:17:23 in 题解