APIO10A – spoj

Đề bài: http://www.spoj.com/problems/APIO10A/


Cho 1 dãy N số nguyên. Một hàm số bậc 2 : f(x) = a * x ^ 2 + b * x + c. Phân dãy trên thành các đoạn liên tiếp sao cho tổng các hàm f trên các dãy là lớn nhất (giá trị f của 1 dãy là f(x) với x là tổng của dãy đó).

Input format :

  • Dòng đầu là số test case T
  • Mỗi test case gồm 3 dòng :
    • Dòng đầu là số nguyên dương N – số phần tử của dãy.
    • Dòng 2 là 3 số nguyên a, b, c.
    • Dòng còn lại gồm n số x1, x2, …, xn là n phần tử của dãy.

Output format :

  • Mỗi test case gồm 1 dòng, là kết quả của bài toán.

Giới hạn :

T<=3

n ≤ 1, 000, 000,

−5 ≤ a ≤ −1

b <= 10,000,000

c <= 10,000,000

1 ≤ xi ≤ 100.

Thuật toán:


Gọi f(x) = a * x ^ 2 + b * x + c

Thuật O(n^2):

Gọi dp(i) là chi phí lớn nhất khi phân hoạch đoạn từ 1 -> i.

sum(i) là tổng các phần tử từ 1 -> i.

dp(i) = max(dp(j) + f(sum(i) – sum(j)) (1 <= i <= n; 0 <= j < i)

 

Thuật O(n): dùng Convex Hull Trick

dp(i) = max(dp(j) + f(sum(i) – sum(j)) (1 <= i <= n; 0 <= j < i)

⇔ dp(i) = dp(j) + a * (sum(i) – sum(j))^ 2 + b * (sum(i) – sum(j)) + c

⇔ dp(i) = (a * sum(i) ^ 2 + b * sum(i) + c) + (-2 * a * sum(i) * sum(j)) + a * sum(j) ^ 2 – b * sum(j) ^ 2

Đặt A = -2 * a * sum(j), X = sum(i), B = a * sum(j) ^ 2 – b * sum(j) ^ 2

⇔ ta được đường thẳng y = A * X + B.

Vì mảng sum tăng dần -> ta có thể dùng two-pointer để giảm đpt xuống O(n)

Code:


#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 10;
 
class ConvexHull {
private:
    int head, tail;
    long long A[N], B[N];
public:
    void init() { head = tail = 0; }
    bool bad(int l1, int l2, int l3) {
        return (long double) (B[l3] - B[l1]) / (A[l1] - A[l3]) < (long double) (B[l2] - B[l1]) / (A[l1] - A[l2]);
    }
    void add(long long a, long long b) {
        A[tail] = a; B[tail++] = b;
        while (tail > 2 && bad(tail - 3, tail - 2, tail - 1)) {
            A[tail - 2] = A[tail - 1];
            B[tail - 2] = B[tail - 1];
            tail--;
        }
    }
    long long query(long long x) {
        if (head >= tail) head = tail - 1;
        while (head < tail - 1
               && A[head + 1] * x + B[head + 1] >= A[head] * x + B[head]) head++;
        return A[head] * x + B[head];
    }
} hull;
 
int n, a, b, c;
long long sum[N];
 
long long f(long long x) { return a * x * x + b * x + c; }
 
void load() {
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", sum + i);
        sum[i] += sum[i - 1];
    }
}
 
void process() {
    hull.init();
    long long cost = f(sum[1]);
    hull.add(-2 * a * sum[1], cost + a * sum[1] * sum[1] - b * sum[1]);
 
    for (int i = 2; i <= n; ++i) {
        cost = f(sum[i]) + max(0ll, hull.query(sum[i]));
        hull.add(-2 * a * sum[i], cost + a * sum[i] * sum[i] - b * sum[i]);
    }
    printf("%lld\n", cost);
}
 
int main() {
  //  freopen("input.in", "r", stdin);
 //   freopen("output.out", "w", stdout);
 
    int test; scanf("%d", &test);
    while (test--) {
        load();
        process();
    }
 
    return 0;
}