针对 LeetCode 3826“最小分割分数”这里提供斜率优化 (Convex Hull Trick) 的 C 实现时间复杂度 O(k * n)空间复杂度 O(n)。---核心思路1. 状态定义dp_prev[i] 表示将前 i 个元素分成当前段数的最优两倍分数避免浮点数。2. 转移方程变形· 令前缀和 pref[i]最后一段起点为 jj 为前一段结束位置。· 转移dp_cur[i] min{ dp_prev[j] (pref[i]-pref[j])*(pref[i]-pref[j]1) }· 展开并整理为关于 pref[i] 的一次函数· 斜率 m -2 * pref[j]· 截距 c dp_prev[j] pref[j]^2 - pref[j]· 则原式 m * pref[i] c pref[i]^2 pref[i]3. 维护下凸包所有候选 j 对应一条直线用单调双端队列维护下凸包每次查询 x pref[i] 处的最小值。---C 代码实现cpp#include vector#include deque#include climitsusing namespace std;class Solution {public:long long minPartitionScore(vectorint nums, int k) {int n nums.size();vectorlong long pref(n 1, 0);for (int i 0; i n; i) {pref[i 1] pref[i] nums[i];}// dp_prev: 分成 1 段时的两倍分数vectorlong long dp_prev(n 1, 0);for (int i 1; i n; i) {long long s pref[i];dp_prev[i] s * (s 1); // 两倍分数}// 迭代分段数 2 .. kfor (int seg 2; seg k; seg) {vectorlong long dp_cur(n 1, LLONG_MAX / 4);dequepairlong long, long long hull; // 存储直线 (斜率, 截距)for (int i 1; i n; i) {int j i - 1; // 新候选直线的下标if (j 1) {long long m -2 * pref[j];long long c dp_prev[j] pref[j] * pref[j] - pref[j];// 将新直线加入凸包维护下凸性while (hull.size() 2) {auto [m1, c1] hull[hull.size() - 2];auto [m2, c2] hull[hull.size() - 1];// 检查新直线是否使倒数第二条直线无用// 条件: (c2 - c1) * (m1 - m) (c - c1) * (m1 - m2)if ((c2 - c1) * (m1 - m) (c - c1) * (m1 - m2)) {hull.pop_back();} else {break;}}hull.push_back({m, c});}// 查询 x pref[i] 处的最优直线队首while (hull.size() 2) {auto [m1, c1] hull[0];auto [m2, c2] hull[1];if (m1 * pref[i] c1 m2 * pref[i] c2) {hull.pop_front();} else {break;}}if (!hull.empty()) {auto [m, c] hull.front();dp_cur[i] m * pref[i] c pref[i] * pref[i] pref[i];} else {dp_cur[i] LLONG_MAX / 4; // 不可能状态}}dp_prev.swap(dp_cur);}return dp_prev[n] / 2; // 除以2得到原始分数}};---复杂度分析· 时间复杂度O(k * n)每个状态进出队列一次总操作线性。· 空间复杂度O(n)存储前缀和、DP数组以及凸包队列。---注意事项· 所有计算使用 long long 避免溢出。· 计算过程中存储两倍分数最后除以2避免浮点数运算。· 该实现假设 nums 中元素非负保证 pref[i] 单调递增从而可安全使用队首弹出策略。若可能出现负数需改用二分查找凸包但原题通常满足非负条件。如果题目允许负数只需将查询部分改为二分查找即可但代码会稍复杂。上述实现适用于绝大多数情况。
针对 LeetCode 3826“最小分割分数”这里提供斜率优化 (Convex Hull Trick) 的 C 实现时间复杂度 O(k * n)空间复杂度 O(n)。---核心思路1. 状态定义dp_prev[i] 表示将前 i 个元素分成当前段数的最优两倍分数避免浮点数。2. 转移方程变形· 令前缀和 pref[i]最后一段起点为 jj 为前一段结束位置。· 转移dp_cur[i] min{ dp_prev[j] (pref[i]-pref[j])*(pref[i]-pref[j]1) }· 展开并整理为关于 pref[i] 的一次函数· 斜率 m -2 * pref[j]· 截距 c dp_prev[j] pref[j]^2 - pref[j]· 则原式 m * pref[i] c pref[i]^2 pref[i]3. 维护下凸包所有候选 j 对应一条直线用单调双端队列维护下凸包每次查询 x pref[i] 处的最小值。---C 代码实现cpp#include vector#include deque#include climitsusing namespace std;class Solution {public:long long minPartitionScore(vectorint nums, int k) {int n nums.size();vectorlong long pref(n 1, 0);for (int i 0; i n; i) {pref[i 1] pref[i] nums[i];}// dp_prev: 分成 1 段时的两倍分数vectorlong long dp_prev(n 1, 0);for (int i 1; i n; i) {long long s pref[i];dp_prev[i] s * (s 1); // 两倍分数}// 迭代分段数 2 .. kfor (int seg 2; seg k; seg) {vectorlong long dp_cur(n 1, LLONG_MAX / 4);dequepairlong long, long long hull; // 存储直线 (斜率, 截距)for (int i 1; i n; i) {int j i - 1; // 新候选直线的下标if (j 1) {long long m -2 * pref[j];long long c dp_prev[j] pref[j] * pref[j] - pref[j];// 将新直线加入凸包维护下凸性while (hull.size() 2) {auto [m1, c1] hull[hull.size() - 2];auto [m2, c2] hull[hull.size() - 1];// 检查新直线是否使倒数第二条直线无用// 条件: (c2 - c1) * (m1 - m) (c - c1) * (m1 - m2)if ((c2 - c1) * (m1 - m) (c - c1) * (m1 - m2)) {hull.pop_back();} else {break;}}hull.push_back({m, c});}// 查询 x pref[i] 处的最优直线队首while (hull.size() 2) {auto [m1, c1] hull[0];auto [m2, c2] hull[1];if (m1 * pref[i] c1 m2 * pref[i] c2) {hull.pop_front();} else {break;}}if (!hull.empty()) {auto [m, c] hull.front();dp_cur[i] m * pref[i] c pref[i] * pref[i] pref[i];} else {dp_cur[i] LLONG_MAX / 4; // 不可能状态}}dp_prev.swap(dp_cur);}return dp_prev[n] / 2; // 除以2得到原始分数}};---复杂度分析· 时间复杂度O(k * n)每个状态进出队列一次总操作线性。· 空间复杂度O(n)存储前缀和、DP数组以及凸包队列。---注意事项· 所有计算使用 long long 避免溢出。· 计算过程中存储两倍分数最后除以2避免浮点数运算。· 该实现假设 nums 中元素非负保证 pref[i] 单调递增从而可安全使用队首弹出策略。若可能出现负数需改用二分查找凸包但原题通常满足非负条件。如果题目允许负数只需将查询部分改为二分查找即可但代码会稍复杂。上述实现适用于绝大多数情况。
