题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=3507

题目大意

给定n个数，找到一个序列，使得 [sigma(1, k)Ci^2] + M 最小。

题解

[sigma(1, k)Ci^2] + M

Sk = sigma(1, i)Ci

f[i] = min{f[j] + (s[i] - s[j])^2 + M}

g[pos] = f[pos] + (s[i] - s[pos])^2 + M

when j < k, if g[k] better than g[j] then g[k] < g[j]

so g[pos] = f[pos] + (s[i] - s[pos])^2 + M

=> f[k] + (s[i] - s[k])^2 + M < f[k] + (s[i] - s[k])^2 + M

=> f[k] - f[j] + s[k]^2 - s[j]^2 < 2*s[i]*(s[k] - s[j])

as we know s[k] > s[j], so

=> (f[k] - f[j] + s[k]^2 - s[j]^2)/(s[k] - s[j]) < 2*s[i]

=> (f[j] - f[k] + s[j]^2 - s[k]^2)/(s[j] - s[k]) < 2*s[i]

so the left part is slope[j, k] = (f[j] - f[k] + s[j]^2 - s[k]^2)/(s[j] - s[k])

now we know when j < k, if k better then j then slope[j, k] < 2*s[i], or vice versa

after that we consider three point j, k, l, when j < k < l

if slope[j, k] > slope[k, l] then:

1. if slope[k, l] < 2*s[i] then l is better than k

2. if slope[k, l] > 2*s[i] then slope[j, k] > 2*s[i] too, so j is no worse then k

In summary, if slope[j, k] > slope[k, l] then k is useless

代码 

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <cctype>
#include <climits>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
//#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;

/* quick input */
template <class T>
bool scan_d(T &ret){
    char c;
    int sgn;
    T bit = 0.1;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && c != '.' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret*10 + (c - '0');
    if (c == ' ' || c == '\n') {
        ret *= sgn;
        return 1;
    }
    while (c = getchar(), c >= '0' && c <= '9') {
        ret += (c - '0')*bit;
        bit /= 10;
    }
    ret *= sgn;
    return 1;
}
/* end - quick input */

const int N = 500000;
const long long inf = 1LL<<63;
long long f[N + 5], s[N + 5];
int q[N + 5];

long long slope(int j, int k) {
    if (s[j] == s[k]) {
        if (f[j] >= f[k]) return -inf;
        return inf;
    }
    return (f[j] - f[k] + s[j]*s[j] - s[k]*s[k])/(s[j] - s[k]);
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        s[0] = 0;
        for (int i = 1; i <= n; ++i) {
            long long c;
            scanf("%lld", &c);
            s[i] = s[i - 1] + c;
        }
        
        int head = 0, tail = 0;
        f[0] = 0;
        q[0] = 0;
        for (int i = 1; i <= n; ++i) {
            while (head < tail && slope(q[head], q[head + 1]) < 2*s[i]) ++head;
            f[i] = f[q[head]] + (s[i] - s[q[head]])*(s[i] - s[q[head]]) + (long long)m;
            while (head < tail && slope(q[tail - 1], q[tail]) > slope(q[tail], i)) --tail;
            q[++tail] = i;
        }
        printf("%lld\n", f[n]);
    }
    return 0;
}
转载保留版权：http://haipz.com/blog/i/6519 - 海胖博客