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

时间：2022-01-01 09:47:32

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

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

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

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

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

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

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

如果令 y(i)=dp[i]+sum[i]2,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(n2)的复杂度降成了线性！没有比这更激动人心的了

#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;

}

　　

相关文章