BZOJ/1010.c

   1 /**************************************************************
   2     Problem: 1010
   3     User: dennisyang
   4     Language: C
   5     Result: Accepted
   6     Time:176 ms
   7     Memory:1732 kb
   8 ****************************************************************/
   9
  10 /*
  11 dp[i] = min{dp[j-1] + (i - j + sigma(c[k],j<=k<=i) - L)^2}
  12
  13 s[i] = sigma(c[k],1<=k<=i) + i
  14 l = L + 1
  15
  16 dp[i] = min{dp[j-1] + (s[i]-s[j-1]-l)^2}
  17 dp[k-1]+(s[i]-s[k-1]-l)^2 < dp[j-1] + (s[i]-s[j-1]-l)^2
  18 dp[k-1] + s[k-1]^2 - 2*s[i]*s[k-1] + 2*s[k-1]*l < dp[j-1] + s[j-1]^2 - 2*s[i]*s[j-1] + 2*s[j-1]*l
  19 dp[k-1] + s[k-1]^2 + 2*s[k-1]*l - (dp[j-1] + s[j-1]^2 + 2*s[j-1]*l) < 2*s[i]*(s[k-1]-s[j-1])
  20 y(k) = dp[k-1] + s[k-1]^2 + 2*s[k-1]*l
  21 x(k) = 2*s[k-1]
  22 y(k) - y(j) < s[i] * (x(k) - x(j))
  23
  24 slope = (y(k) - y(j)) / (x(k) - x(j))
  25
  26 j<k (x(k) > x(j))
  27     slope < s[i]
  28 j>k (x(k) < x(j))
  29     slope > s[i]
  30 */
  31 #include <stdio.h>
  32
  33 #define sqr(x) ((x)*(x))
  34 #define maxn 50001
  35
  36 typedef long long int64;
  37
  38 int n,queue[maxn];
  39 int64 l,s[maxn],dp[maxn];
  40
  41 inline double y(int p) {
  42     return dp[p-1] + sqr(s[p-1]) + 2*l*s[p-1];
  43 }
  44
  45 inline double x(int p) {
  46     return 2*s[p-1];
  47 }
  48
  49 inline double slope(int p, int q) {
  50     return (y(p) - y(q)) / (x(p) - x(q));
  51 }
  52
  53 int main() {
  54     scanf("%d%lld",&n,&l);
  55     ++l;
  56     int i;
  57     for (i=1; i<=n; ++i) scanf("%lld",s+i);
  58     for (i=1; i<=n; ++i) s[i] += s[i-1];
  59     for (i=1; i<=n; ++i) s[i] += i;
  60     int *qf = &queue[1], *qr = &queue[0];
  61     for (i=1; i<=n; ++i) {
  62         while (qf < qr && slope(*(qr-1),*qr) > slope(*qr,i)) --qr;
  63         *++qr = i;
  64         while (qf < qr && slope(*qf,*(qf+1)) < s[i]) ++qf;
  65         dp[i] = dp[*qf - 1] + sqr(s[i] - s[*qf - 1] - l);
  66     }
  67     printf("%lld\n",dp[n]);
  68     return 0;
  69 }