DeepSeek LeetCode 3826. 最小分割分数 C++实现

针对 LeetCode 3826“最小分割分数”，这里提供斜率优化 (Convex Hull Trick) 的 C++ 实现，时间复杂度 O(k * n)，空间复杂度 O(n)。

---

核心思路

1. 状态定义：dp_prev[i] 表示将前 i 个元素分成当前段数的最优两倍分数（避免浮点数）。
2. 转移方程变形：
· 令前缀和 pref[i]，最后一段起点为 j（j 为前一段结束位置）。
· 转移：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 <climits>
using namespace std;

class Solution {
public:
long long minPartitionScore(vector<int>& nums, int k) {
int n = nums.size();
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + nums[i];
}

// dp_prev: 分成 1 段时的两倍分数
vector<long 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 .. k
for (int seg = 2; seg <= k; ++seg) {
vector<long long> dp_cur(n + 1, LLONG_MAX / 4);
deque<pair<long 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] 单调递增），从而可安全使用队首弹出策略。若可能出现负数，需改用二分查找凸包，但原题通常满足非负条件。

如果题目允许负数，只需将查询部分改为二分查找即可，但代码会稍复杂。上述实现适用于绝大多数情况。