维修机器人

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<algorithm>
  6 using namespace std;
  7 const int MAXN=101000;
  8 const long long oo=20000000;
  9 long long h[MAXN];
 10 int n;
 11 long long st[MAXN][30];
 12 int pow2[21];
 13 int lg[MAXN];
 14 long long cost;
 15 long long sum[MAXN];
 16 long long sumsqr[MAXN];
 17 void init_st()
 18 {
 19     pow2[0]=1;
 20     for(int i=1;i<=20;i++)pow2[i]=pow2[i-1]*2;
 21     int p=-1;
 22     for(int j=1;j<=n;j++)
 23     {
 24         st[j][0]=h[j];
 25         if(j==pow2[p+1])p++;
 26         lg[j]=p;
 27     }
 28     for(int k=1;pow2[k]<=n;k++)
 29     {
 30         for(int j=1;j+pow2[k]-1<=n;j++)
 31         st[j][k]=max(st[j][k-1],st[j+pow2[k-1]][k-1]);
 32     }
 33 }
 34 int RMQ(int a,int b)
 35 {
 36     int del=b-a+1;
 37     del=lg[del];
 38     return max(st[a][del],st[b-pow2[del]+1][del]);
 39 }
 40 void init_sum()
 41 {
 42     sum[0]=sumsqr[0]=0;
 43     for(int i=1;i<=n;i++)
 44     {
 45         sum[i]=sum[i-1]+h[i];
 46         sumsqr[i]=sumsqr[i-1]+(long long)h[i]*(long long)h[i];
 47     }
 48 }
 49 void init()
 50 {
 51     scanf("%d%I64d",&n,&cost);
 52     for(int i=1;i<=n;i++)scanf("%I64d",&h[i]);
 53     h[0]=h[n+1]=oo;
 54     init_st();
 55     init_sum();
 56 }
 57 
 58 int stack[MAXN],top;
 59 long long f[MAXN];
 60 long long fmin(long long A,long long B,long long C,long long mn,long long mx)
 61 {
 62     long long ret=oo*oo;
 63     long long topx=(-B)/(2*A);
 64     for(int i=0;i<=1;i++)
 65     {
 66         if(mn<=topx&&topx<=mx)ret=min(ret,A*topx*topx+B*topx+C);
 67         topx++;
 68     }
 69     ret=min(ret,min(A*mn*mn+B*mn+C,A*mx*mx+B*mx+C));
 70     return ret;
 71 }
 72 long long H(int a,int b)
 73 {
 74     if(a==b-1)return cost*abs(h[b]-h[a]);
 75     int mn=RMQ(a+1,b-1)+1;
 76     int mx=min(h[a],h[b]);
 77     long long A=b-a-1,
 78                  B=-2*(sum[b-1]-sum[a]),
 79                 C=sumsqr[b-1]-sumsqr[a];
 80     if(a!=0)B-=cost,C+=cost*h[a];
 81     if(b!=n+1)B-=cost,C+=cost*h[b];
 82     return fmin(A,B,C,mn,mx);
 83 }
 84 void work()
 85 {
 86     top=0;
 87     stack[top++]=0;
 88     stack[top++]=1;
 89     f[1]=0;
 90     for(int i=2;i<=n+1;i++)
 91     {
 92         if(i!=n+1)f[i]=f[i-1]+cost*abs(h[i]-h[i-1]);
 93         else f[i]=f[i-1];
 94         while(h[stack[top-1]]<h[i])
 95         {
 96             f[i]=min(f[i],f[stack[top-1]]+H(stack[top-1],i));
 97             top--;
 98         }
 99         f[i]=min(f[i],f[stack[top-1]]+H(stack[top-1],i));
100         if(h[stack[top-1]]==h[i])top--;
101         stack[top++]=i;
102     }
103     printf("%I64d
",f[n+1]);
104 }
105 int main()
106 {
107     freopen("repair.in","r",stdin);
108     freopen("repair.out","w",stdout);
109     init();
110     work();
111 }

**对于这道题哇。我当初想的特别美好。看到样例我以为就是从左往右轮遇到最大的就把前面的值全变成这个值然后计算代价啥的哇，然后继续轮。。后来是我天真了。。。

***题解说：只有当 a > b 且 c > b 时，才可能对 b 进行调整，否则将b 增大不可能减小差值导致的代价，另一方面还有调整本身的代价，那么不妨设

b < c≤a。

另外一个显然的结论是，b 调整后不会超过 c，否则的话将 b 的调整量减小，调整的代价减小，差值的代价不会增大，整个方案会更优。

所以仅当 b < a 且 b < c 时需要进行调整，设调整后的数为 B，那么 B 的范围为［ b, min(a,c) ］ ( 将不调整也算入 ) 。调整后的总代价为

cost(B)=(B-b)2+(a-B)×C+(c-B)×C，这是一个二次函数，B 有确定的取值范围，要对其进行最优化是很容易的。

再到后来题解又转到了单调队列。RMQ啥的。。

实际上刚好符合单调队列的结构：从前往后扫描，维护单降队列，则每次插入一个元素时，从队首踢出的元素就是第二类转移的位置，踢完后队首的元素就是第一类转移的位置，而且也不需要专门实现一个 RMQ，每次转移时从队列中踢出的前一个元素就是 RMQ 的值。

然后这道题就结束了？！。。。。。先持保留意见等我哪天脑子灵光了估计可能就看懂了。。然后就可以翻译成我的小仙语啦。。。。