【题解】hdu3507：Print Article

原题传送门
斜率优化
令$s_i={\sum }_{j=1}^i{c}_j$
可以写出一个非常显然的dp方程：$d{p}_i=min(d{p}_j+(s_i-s_j{)}^2)+M$
接下来固定套路
设两个决策$x,y(x>y)$，如果x比y更优必须满足
$d{p}_x+(s_i-s_x{)}^2<d{p}_y+(s_i-s_y{)}^2$
化简得$\frac{(d{p}_x-s_x^2)-(d{p}_y-s_y^2)}{2(s_x-s_y)}<s_i$
然后单调队列维护就行了

结果，我死活过不了，莫名其妙的wa掉也是一脸懵逼
去网上找了篇题解对拍没有问题，那就算了吧
Code：

#include <bits/stdc++.h>
#define maxn 500010
#define LL long long
using namespace std;
LL n, m, s[maxn], q[maxn], dp[maxn];

inline LL read(){
    LL s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

double slope(int x, int y){ return 1.0 * (dp[x] + s[x] * s[x] - dp[y] - s[y] * s[y]) / 2LL / (s[x] - s[y]); }

int main(){
    while (scanf("%d%d", &n, &m) == 2){
        for (int i = 1; i <= n; ++i) s[i] = read(), s[i] += s[i - 1];
        int h = 0, t = 0;
        for (int i = 1; i <= n; ++i){
            while (h < t && slope(q[h + 1], q[h]) < s[i]) ++h;
            dp[i] = dp[q[h]] + (s[i] - s[q[h]]) * (s[i] - s[q[h]]) + m;
            while (h < t && slope(q[t], q[t - 1]) > slope(i, q[t])) --t;
            q[++t] = i;
        }
        printf("%lld\n", dp[n]);
    }
    return 0;
}