[hdu3507 Print Article]斜率优化dp入门

题意：需要打印n个正整数，1个数要么单独打印要么和前面一个数一起打印，1次打印1组数的代价为这组数的和的平方加上常数M。求最小代价。

思路：如果令dp[i]为打印前i个数的最小代价，那么有

dp[i]=min(dp[j]+(sum[i]-sum[j])²+M),j<i

直接枚举转移是O(n²)的，然而这个方程可以利用斜率优化将复杂度降到O(n)。

根据斜率优化的一般思路，对当前考虑的状态i，考虑决策j和k(j<k)，如果k比j优，那么根据转移方程有：dp[k]+(sum[i]-sum[k])²+M ≤ dp[j]+(sum[i]-sum[j])²+M

整理可得：dp[k]+sum[k]²-2*sum[i]*sum[k] ≤ dp[j]+sum[j]²-2*sum[i]*sum[j] 

然后进一步得到：[(dp[k]+sum[k]²)-(dp[j]+sum[j]²)] / (2*sum[k] - 2*sum[j]) ≤ sum[i]

如果令 y(i)=dp[i]+sum[i]²,x(i)=2*sum[i]，那么有：( y(k)-y(j) ) / ( x(k)-x(j) ) ≤ sum[i]，不妨令左边=G[j][k]，即"j到k的斜率",G[j][k] ≤ sum[i]

注意，上面的推理的因果是等价的，也就是说 "k比j优" ↔ "( y(k)-y(j) ) / ( x(k)-x(j) ) ≤ sum[i]成立"

如果从小到大计算每个状态，那么(1)在某次计算状态i时，k比j优，由于sum数组单调递增，所以在以后的状态计算里面k都比j优(2)考虑三个状态i,j,k(i<j<k)，满足G[i][j]≥G[j][k]，那么在计算状态t(>k)的时候，{ 假设G[j][k]≤sum[t]，k就比j优，否则G[j][k]>sum[t]，那么显然有G[i][j]>sum[t]，所以j不比i优 }，所以对于t>k而言，j既没有k优也没有i优，完全可以舍弃。

在（2）的约束下，所有可能成为子状态的点构成了1个凸包，假设当前在计算状态i，这个凸包中最“前面”的两个点依次为j,k，如果G[j][k]≤sum[i]，那么k比j优，把i从凸包里面删掉然后继续这样考虑，否则有G[j][k]>sum[i]，说明j是最优的，因为对任意t∈(k,i)&&t∈凸包，都有G[j][t]>G[j][k]>sum[i]，也就是没有比j更优的了。

虽然推理过程比较多，但是最后的结论非常的优美，程序也非常短，更重要的是，直接将原来O(n²)的复杂度降成了线性！没有比这更激动人心的了

#include <bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define mset(a, x) memset(a, x, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(b))
#define cas() int T, cas = 0; cin >> T; while (T --)
template<typename T>bool umax(T&a, const T&b){return a<b?(a=b,true):false;}
template<typename T>bool umin(T&a, const T&b){return b<a?(a=b,true):false;}
typedef long long ll;
typedef pair<int, int> pii;
#ifndef ONLINE_JUDGE
    #include "local.h"
#endif
const int N = 5e5 + 7;
int head, tail;
pii q[N];
int n, m, x, sum[N];

int sqr(int x) { return x * x;}
int getY(int p) { return q[p].second + sqr(sum[q[p].first]); }
int getX(int p) { return 2 * sum[q[p].first]; }
int up(int p) { return getY(p + 1) - getY(p); }
int down(int p) { return getX(p + 1) - getX(p); }
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i ++) {
            scanf("%d", &x);
            sum[i] = sum[i - 1] + x;
        }
        head = tail = 0;
        q[tail ++] = mp(0, 0);
        for (int i = 1; i <= n; i ++) {
            while (tail - head > 1 && up(head) <= down(head) * sum[i]) head ++;
            q[tail ++] = mp(i, q[head].second + sqr(sum[i] - sum[q[head].first]) + m);
            while (tail - head > 2 && up(tail - 3) * down(tail - 2) >= up(tail - 2) * down(tail - 3)) {
                swap(q[tail - 2], q[tail - 1]);
                tail --;
            }
        }
        cout << q[tail - 1].second << endl;
    }
    return 0;
}