HDU 3507 Print Article （斜率优化）

ACM

题目地址：
HDU 3507 Print Article

题意：
给定一个长度为n的序列，和一个常数m，我们可以将序列分成随意段，每段的权值为sum(arr[i]) + C(x<=i<=y)，求一种划分方法使得整个序列的权值最小

分析：
from：亟隐's blog

f[i]=min(f[k]+(sum(i)-sum(k))^2 )+m
= f[k]+sum^2(i)+sum^2(k)-2*sum(i)*sum(k)+m.
也就是找一个最小的f[k]+sum^2(k)-2*sum(i)*sum(k),如果k优于j,必有(f[k]+sum^2(k)-f[j]-sum^2(j))/(2*sum(k)-2*sum(j))<=s[i].

代码：

/*
*  Author:      illuz 
  
   
*  File:        3507.cpp
*  Create Date: 2014-09-19 10:19:57
*  Descripton:  dp
*/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int N = 5e6 + 10; int n, m, l, r, q[N]; ll s[N], x[N], y[N], k[N]; void init() { int x; repf (i, 1, n) { cin >> x; s[i] = s[i - 1] + x; k[i] = s[i] * 2; } } inline bool check(int a, int b, int c) { return (y[a] - y[b]) * (k[b] - k[c]) <= (y[b] - y[c]) * (k[a] - k[b]); } void solve() { q[0] = l = r = 0; repf (i, 1, n) { while (l < r && (y[q[l+1]]-y[q[l]]) <= s[i] * (k[q[l+1]]-k[q[l]])) l++; x[i] = x[q[l]] + (s[i] - s[q[l]]) * (s[i] - s[q[l]]) + m; y[i] = x[i] + s[i] * s[i]; while (l < r && check(i, q[r], q[r-1])) r--; q[++r] = i; } cout << x[n] << endl; } int main() { ios_base::sync_with_stdio(0); while (cin >> n >> m) { init(); solve(); } return 0; }