凸包优化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(vectorint nums, int k) {int n nums.size();vectorint sum(n 1); // nums 的前缀和partial_sum(nums.begin(), nums.end(), sum.begin() 1);vectorlong long f(n 1, LLONG_MAX / 2);f[0] 0;vectorvec q(n - k 2);for (int K 1; K k; K) {int head 0, tail 0; // 模拟 dequelong long s sum[K - 1];q[tail] vec{s, f[K - 1] s * s - s};for (int i K; i n - (k - K); i) { // 其他子数组的长度至少是 1s 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;}};
)
