G6025 [GESP202609 六级] 数组划分 题解

知识点：动态规划、前缀和、区间代价。

解题思路

以前缀和s支持区间和，dp[i]为前i项划分的最小代价，枚举末段起点j+1，转移dp[j]+(s[i]-s[j])²。

为什么正确

任何划分都有唯一末段，移除末段后的前缀可以独立取最优，遍历全部j覆盖所有划分。

易错点

数组可有负数，不能贪心把每项单独分段；区间和、平方和状态用long long。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long>s(n+1),dp(n+1,1LL<<60);
    for(int i=1;i<=n;i++) {
        cin>>s[i];
        s[i]+=s[i-1];
    }
    dp[0]=0;
    for(int i=1;i<=n;i++)for(int j=0;j<i;j++)dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*(s[i]-s[j]));
    cout<<dp[n];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。