凸包优化dp|partial_sum

lc3826

抽象为点积->凸包 投影

差集 下凸包

划分型dp f k i (fk-1 j) + (si-j)

struct vec {
long long x, y;
};

vec sub(vec a, vec b) {
return vec{a.x - b.x, a.y - b.y};
}

long long dot(vec a, vec b) {
return a.x * b.x + a.y * b.y;
}

// 如果乘法会溢出，用 __int128
__int128 det(vec a, vec b) {
return (__int128) a.x * b.y - (__int128) a.y * b.x;
}

class Solution {
public:
long long minPartitionScore(vector<int>& nums, int k) {
int n = nums.size();
vector<int> sum(n + 1); // nums 的前缀和
partial_sum(nums.begin(), nums.end(), sum.begin() + 1);

vector<long long> f(n + 1, LLONG_MAX / 2);
f[0] = 0;

vector<vec> q(n - k + 2);

for (int K = 1; K <= k; K++) {
int head = 0, tail = 0; // 模拟 deque

long long s = sum[K - 1];
q[tail++] = vec{s, f[K - 1] + s * s - s};

for (int i = K; i <= n - (k - K); i++) { // 其他子数组的长度至少是 1
s = sum[i];
vec p = {-2 * s, 1};
while (tail - head > 1 && dot(p, q[head]) >= dot(p, q[head + 1])) {
head++;
}

vec v{s, f[i] + s * s - s};
f[i] = dot(p, q[head]) + s * s + s;

while (tail - head > 1 && det(sub(q[tail - 1], q[tail - 2]), sub(v, q[tail - 1])) <= 0) {
tail--;
}
q[tail++] = v;
}
}

return f[n] / 2;
}
};