太棒了！为了让你能直接在 OJ（如 Hydro、HUSTOJ、DOMJudge 等）上部署这道**【最多划分 K 次】**的变体题，我为你量身定制了这套 C++ 数据生成器。

由于本题允许负数，并且核心考点在于**“最多划分 K 次时，分得越多不一定越好”**，我在测试点设计上加入了极具杀伤力的“全负数”、“正负交替”等防假算法数据。

🎯 1~10 号测试点设计蓝图 (精准拦截错误代码)

1. Test 1 & 2：样例数据。确保选手理解了“负数情况下少划分收益更大”的逻辑。
2. Test 3：极小规模边界 (N=1, K=1, A_1=-9999)。测试基本的数组越界与负数初始化是否正确。
3. Test 4：全负数深坑 (N=100, K=100)。数组全是负数。贪心算法或没理解“最多”概念的选手，会错误地把数组切成 100 段，导致累加了 100 个负数，从而得到极小值；正确的代码会自动停在只切 1 段或极少段。
4. Test 5：全零测试 (N=100, K=50)。测试 0 均值的处理，防止某些代码在浮点数精度比较时出现正负 0.0 误判。
5. Test 6：正负交替 (N=100, K=20)。极端的 10000, -10000, 10000... 交替。极其考验 DP 状态转移寻找最优分割点的能力。
6. Test 7：单一划分边界 (N=100, K=1)。强行限制只能切 1 刀，测试边界 j=1 时的逻辑。
7. Test 8：全划分边界 (N=100, K=100)。随机正负数混杂。
8. Test 9：单调递减跨越零点 (N=100, K=30)。例如 10000, 9800 ... -9800。针对部分贪心策略（如“遇到负数就不切”）进行针对性 Hack。
9. Test 10：满状态随机极限数据 (N=100, K=50)。元素在 $[-10^4, 10^4]$ 完全随机，测试最终的时间复杂度（要求 $O(N^2 K)$）和整体稳定性。

💻 完整数据生成器 C++ 代码 (generator.cpp)

请将以下代码保存为 generator.cpp 并使用 C++14/17 编译运行。它将瞬间在同目录下生成 20 个文件（1.in ~ 10.out）。

#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <string>
#include <random>
#include <algorithm>

using namespace std;

// ---------------------------------------------------------
// 核心解题函数：用于生成标准答案 (.out 文件)
// 完全采用非递归二维 DP，绝对避免爆栈，且杜绝除零风险
// ---------------------------------------------------------
double solveDP(int n, int k_max, const vector<int>& a) {
    vector<double> prefix(n + 1, 0.0);
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + a[i - 1]; // 注意: a 是 0-based
    }

    // 初始化 DP 表为极小值（由于最小单体均值为 -10000，累加100次也才 -10^6，-1e9足够安全）
    vector<vector<double>> dp(n + 1, vector<double>(k_max + 1, -1e9));
    
    // Base Case: 划分 1 段
    for (int i = 1; i <= n; ++i) {
        dp[i][1] = prefix[i] / i; // i 从 1 开始，绝对不会除以 0
    }

    // 状态转移
    for (int j = 2; j <= k_max; ++j) {
        for (int i = j; i <= n; ++i) {
            for (int x = j; x <= i; ++x) {
                // x <= i 保证了 i - x + 1 >= 1，绝对不会触发除以 0 异常
                double avg = (prefix[i] - prefix[x - 1]) / (i - x + 1);
                dp[i][j] = max(dp[i][j], dp[x - 1][j - 1] + avg);
            }
        }
    }
    
    // 收集“最多 K 个”的最优解
    double global_max = -1e9;
    for (int j = 1; j <= k_max; ++j) {
        global_max = max(global_max, dp[n][j]);
    }
    
    return global_max;
}

// ---------------------------------------------------------
// 主生成器逻辑
// ---------------------------------------------------------
int main() {
    // 固定随机种子，保证每次生成数据完全一致，方便复验
    mt19937 rng(20260312); 

    for (int t = 1; t <= 10; ++t) {
        int n, k;
        vector<int> a;
        
        // --- 构造测试用例剧本 ---
        if (t == 1) {
            n = 3; k = 3;
            a = {-10, -10, -10};
        } 
        else if (t == 2) {
            n = 5; k = 3;
            a = {9, 1, 2, 3, 9};
        } 
        else if (t == 3) {
            n = 1; k = 1;
            a = {-9999}; // 极小规模 + 负数边界
        } 
        else if (t == 4) {
            n = 100; k = 100;
            uniform_int_distribution<int> dist(-10000, -1);
            for(int i=0; i<n; ++i) a.push_back(dist(rng)); // 全负数深坑
        } 
        else if (t == 5) {
            n = 100; k = 50;
            for(int i=0; i<n; ++i) a.push_back(0); // 全零边界
        } 
        else if (t == 6) {
            n = 100; k = 20;
            for(int i=0; i<n; ++i) {
                a.push_back((i % 2 == 0) ? 10000 : -10000); // 极端正负交替
            }
        } 
        else if (t == 7) {
            n = 100; k = 1;
            uniform_int_distribution<int> dist(-10000, 10000);
            for(int i=0; i<n; ++i) a.push_back(dist(rng)); // 只能切1刀
        } 
        else if (t == 8) {
            n = 100; k = 100;
            uniform_int_distribution<int> dist(-10000, 10000);
            for(int i=0; i<n; ++i) a.push_back(dist(rng)); // 最多切100刀
        } 
        else if (t == 9) {
            n = 100; k = 30;
            int current = 10000;
            for(int i=0; i<n; ++i) {
                a.push_back(current);
                current -= 200; // 10000, 9800 ... -9800 线性递减
            }
        } 
        else if (t == 10) {
            n = 100; k = 50;
            uniform_int_distribution<int> dist(-10000, 10000);
            for(int i=0; i<n; ++i) a.push_back(dist(rng)); // 终极随机混合测试
        }

        // --- 写入 .in 文件 ---
        string in_filename = to_string(t) + ".in";
        ofstream fout_in(in_filename);
        if (!fout_in.is_open()) {
            cerr << "Error creating file: " << in_filename << endl;
            return 1;
        }
        
        fout_in << n << " " << k << "\n";
        for (int i = 0; i < n; ++i) {
            fout_in << a[i] << (i == n - 1 ? "" : " ");
        }
        fout_in << "\n";
        fout_in.close();

        // --- 运行标准程序并写入 .out 文件 ---
        string out_filename = to_string(t) + ".out";
        ofstream fout_out(out_filename);
        if (!fout_out.is_open()) {
            cerr << "Error creating file: " << out_filename << endl;
            return 1;
        }

        double ans = solveDP(n, k, a);
        
        // NOI 竞赛标准：保留 6 位小数
        fout_out << fixed << setprecision(6) << ans << "\n";
        fout_out.close();

        cout << "Test " << setw(2) << t << " Generated! (N=" << n << ", K=" << k << ") -> Ans: " 
             << fixed << setprecision(6) << ans << endl;
    }

    cout << "All 10 test cases generated successfully! File sizes are minimal (< 20KB total)." << endl;
    return 0;
}

💡 核心防御与优化说明

1. 杜绝除以 0 的可能 (Division by Zero Prevention)：
   • 在基准情况 dp[i][1] = prefix[i] / i 中，i 的范围是 1 到 N，绝不为 0。
   • 在转移方程中，avg 的分母为 (i - x + 1)。由于循环条件设定为 for (int x = j; x <= i; ++x)，意味着 $x \le i$，推导得出 $i - x \ge 0$，因此 $i - x + 1 \ge 1$。分母永远大于等于 1，从数学机制上杜绝了除零异常。
2. 避免爆栈 (Stack Overflow Prevention)：
   • 标准解法 solveDP 函数中只使用了纯粹的 Bottom-Up（自底向上）三重 for 循环，没有任何递归调用 (0 Recursion)，不可能引起 Stack Overflow。
3. 时间与空间极简 (Minimal Time & Space)：
   • 由于没有使用剪枝，算法稳定运行在确定的 $O(N^2K)$ 时间。即便对于 $N=100, K=100$ 的最大输入，计算次数也仅约 $10^6 / 6 \approx 1.6 \times 10^5$ 次，瞬间即可完成，且不需要额外的树图优化技巧。
   • 所有的文本输入、输出加在一起，总物理文件体积小于 20 KB，能被几乎任何 OJ 的测评机极速读取，显著节约评测机 I/O 开销。

太棒了！现在我们就把流程图里的核心思想，真正落实到 NOIP C++14 竞赛标准的代码中。

因为本题允许负数存在，并且要求最多划分 $K$ 次，我们的代码在“极小值初始化”和“答案收集”上会有着和第一题非常关键的不同。

下面我将带你完成 记忆化搜索 $\rightarrow$ 标准二维 DP $\rightarrow$ 极限一维压缩 DP 的三阶进化。每一份代码都可以直接编译运行！

版本一：记忆化搜索 (DFS + 备忘录)

教练点评：对于初学者来说，写 DFS 是最不容易出错的，因为它完全贴合我们人类的思维过程——“大问题拆解成小问题”。但请特别注意，因为本题有负数，备忘录不能再简单地用 -1.0 代表未计算了！ 我们必须额外开一个 visited 数组来标记。

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

const int MAXN = 105;
const double INF = 1e9; // 用 1e9 代表无穷大，-INF 就是负无穷

int n, k_max;
double a[MAXN];
double prefix[MAXN];
double memo[MAXN][MAXN];
bool visited[MAXN][MAXN]; // [易错点 1] 包含负数时，必须用 visited 数组标记是否计算过

// 求解将前 i 个元素，恰好划分为 j 段的最大平均值和
double dfs(int i, int j) {
    // 边界条件：元素不够分
    if (i < j) return -INF;
    
    // 递归终点：只分 1 段
    if (j == 1) {
        return prefix[i] / i; 
    }
    
    // 备忘录剪枝：算过直接返回
    if (visited[i][j]) {
        return memo[i][j];
    }
    
    double max_score = -INF;
    // 尝试最后一段的所有可能起点 x
    for (int x = j; x <= i; ++x) {
        // [关键点 1] O(1) 算出最后一段的平均值 (允许出现负均值)
        double current_avg = (prefix[i] - prefix[x - 1]) / (i - x + 1);
        max_score = max(max_score, dfs(x - 1, j - 1) + current_avg);
    }
    
    visited[i][j] = true;
    return memo[i][j] = max_score;
}

int main() {
    // 优化 C++ I/O 速度，NOIP 竞赛标配
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> n >> k_max)) return 0;
    
    prefix[0] = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    
    // [关键点 2] “最多 K 个”的答案收集方式
    // 我们不能只看 dfs(n, k_max)，必须遍历 1 到 k_max 的所有恰好划分情况
    double global_max = -INF;
    for (int j = 1; j <= k_max; ++j) {
        global_max = max(global_max, dfs(n, j));
    }
    
    cout << fixed << setprecision(6) << global_max << "\n";
    
    return 0;
}

• 时间复杂度：共有 $O(NK)$ 个状态，每个状态向下枚举 $O(N)$ 个分割点，加上前缀和优化，整体为 $O(N^2 K)$。
• 空间复杂度：memo 和 visited 二维数组占用 $O(NK)$，递归调用栈深度最大 $O(K)$，总空间复杂度 $O(NK)$。

版本二：标准二维 DP (Bottom-Up)

教练点评：抛弃了递归的调用开销，这是赛场上最标准、最稳健的写法。我们将状态按照 j（段数）从小到大、i（元素个数）从小到大的顺序推导。

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k_max;
    if (!(cin >> n >> k_max)) return 0;
    
    vector<double> a(n + 1, 0.0);
    vector<double> prefix(n + 1, 0.0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    
    // [易错点 1] 全局初始化为负无穷大 (-1e9)，防止无效状态干扰
    vector<vector<double>> dp(n + 1, vector<double>(k_max + 1, -1e9));
    
    // Base Case：前 i 个元素只分 1 段
    for (int i = 1; i <= n; ++i) {
        dp[i][1] = prefix[i] / i;
    }
    
    // 三重循环开始状态转移
    for (int j = 2; j <= k_max; ++j) {
        for (int i = j; i <= n; ++i) {
            for (int x = j; x <= i; ++x) {
                double avg = (prefix[i] - prefix[x - 1]) / (i - x + 1);
                dp[i][j] = max(dp[i][j], dp[x - 1][j - 1] + avg);
            }
        }
    }
    
    // [关键点 1] "最多 K 个"的答案并不一定在 dp[n][k_max]！
    // 必须从所有合法的 dp[n][1...k_max] 中挑选出最大值
    double global_max = -1e9;
    for (int j = 1; j <= k_max; ++j) {
        global_max = max(global_max, dp[n][j]);
    }
    
    cout << fixed << setprecision(6) << global_max << "\n";
    return 0;
}

• 时间复杂度：严格的三重循环，毫无额外开销，时间复杂度 $O(N^2 K)$。
• 空间复杂度：使用完整的二维表，空间复杂度 $O(NK)$。

版本三：空间优化一维 DP (极限压榨空间)

教练点评：这是本题的最高境界。我们将 $O(NK)$ 的二维数组直接拍扁成 $O(N)$ 的一维数组。并且完美解决了“一维数组会覆盖掉历史记录，导致无法收集最多 K 段答案”的致命陷阱！请仔细看 global_max 是如何接力的！

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k_max;
    if (!(cin >> n >> k_max)) return 0;
    
    vector<double> a(n + 1, 0.0);
    vector<double> prefix(n + 1, 0.0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i];
    }
    
    // 一维滚动数组：初始化为 j=1 时的状态
    vector<double> dp(n + 1, -1e9);
    for (int i = 1; i <= n; ++i) {
        dp[i] = prefix[i] / i;
    }
    
    //[关键点 1] 在这里就先收集一波 j=1 时的答案！
    double global_max = dp[n]; 
    
    for (int j = 2; j <= k_max; ++j) {
        // [易错点 1] 必须倒序遍历！防止左侧的 dp[x-1] 被本轮的新值覆盖
        for (int i = n; i >= j; --i) {
            
            double max_val = -1e9;
            for (int x = j; x <= i; ++x) {
                double avg = (prefix[i] - prefix[x - 1]) / (i - x + 1);
                max_val = max(max_val, dp[x - 1] + avg);
            }
            dp[i] = max_val;
        }
        
        // [关键点 2] 极其重要！每完成一轮 j 的计算，立刻将当前的 dp[n] 提取出来比对！
        // 如果我们等到所有 j 循环都结束再去取，前面 j 比较小但收益可能更高的答案，
        // 早就被后续一维数组的滚动更新给抹除掉了！
        global_max = max(global_max, dp[n]);
    }
    
    cout << fixed << setprecision(6) << global_max << "\n";
    return 0;
}

• 时间复杂度：整体结构依然是三重循环，每次外层循环结束后有一次 $O(1)$ 的答案更新，总时间复杂度为 $O(N^2 K)$。由于 C++ vector 的缓存命中率（Cache Locality）极高，版本三的实际运行速度会比前两个版本更快！
• 空间复杂度：仅使用一维数组，从 $O(NK)$ 飞跃式优化到了 $O(N)$！

🏆 复杂度优化思考与赛场建议

1. 时间优化建议 (常数级优化)： 在内层循环中，我们将 (prefix[i] - prefix[x - 1]) / (i - x + 1) 放在了最深处。由于 prefix[i] 对当前 x 循环是定值，有些极客写法会把它抽离。但在现代编译器的 -O2 优化下，这种简单算术其实没有明显区别。真正的核心优化永远是引入前缀和，将 $O(N)$ 的区间求和转化为 $O(1)$，绝对不要在最内层写 for 循环求和。

2. "恰好"与"最多"的代码形态差异： 对比第一题（恰好）与第二题（最多）的版本三代码，你会发现：

   • 恰好 K 次：只在最后 return dp[n]。
   • 最多 K 次：在每轮 j 结束时抓取 global_max = max(global_max, dp[n])。 这就是算法竞赛的魅力：一行代码的位置变动，代表着完全不同的数学逻辑集合。

理解了上述版本三的代码，说明你对动态规划的“维数压缩”和“历史态收集”已经完全过关了。