洛谷2112题：用动态规划思想解决字符串分割

一、题目解读

洛谷P2112题要求将N个字符串分割为K行，使各行字符总数方差最小。输入包含N个字符串及目标行数K，需输出最小方差除以K的数值（保留一位小数）。题目难点在于高效计算分割方案，需平衡时间复杂度与精度要求。

二、解题思路

用动态规划（DP）求解。核心思想：将问题拆解为“前i个字符串分成j行的最小方差”，利用前缀和优化累计字符数计算，通过状态转移方程递归求解最优解。关键步骤包括预处理、DP状态定义与转移、方差计算。

三、解题步骤

1. 输入与边界处理：读取N、K及字符串长度，若N=0、K=0或K>N直接输出0。

2. 前缀和预处理：构建prefix数组，存储前i个字符串的总长度，减少重复计算。

3. 动态规划初始化：定义dp[i][j]为前i个字符串分成j行的最小方差，初始化dp[0][0]=0。

4. 状态转移：外层循环i遍历字符串数，内层循环j遍历行数，通过k（分割点）枚举子问题，计算当前行字符总数与平均值的偏差平方，更新dp[i][j]=min(dp[k][j-1]+var)。

5. 输出结果：最终解为dp[N][K]，除以K并格式化输出。

四、代码与注释

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <iomanip>
#include <algorithm>
using namespace std;

const double INF = 1e18; // 定义无穷大，用于初始化DP值

int main() {
    int N, K;
    cin >> N >> K;
    
    // 处理特殊情况
    if (N == 0 || K == 0 || K > N) {
        cout << "0.0" << endl;
        return 0;
    }
    
    vector<int> lens(N); // 存储各字符串长度
    for (int i = 0; i < N; ++i) {
        string s;
        cin >> s;
        lens[i] = s.size();
    }
    
    vector<int> prefix(N+1, 0); // 前缀和数组
    for (int i = 1; i <= N; ++i) {
        prefix[i] = prefix[i-1] + lens[i-1];
    }
    
    // dp[i][j]: 前i个单词分成j行的最小方差和
    vector<vector<double>> dp(N+1, vector<double>(K+1, INF));
    dp[0][0] = 0;
    
    double avg = (double)prefix[N] / K; // 总字符数的平均值
    
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= min(K, i); ++j) {
            for (int k = j-1; k < i; ++k) {
                int sum = prefix[i] - prefix[k]; // 当前行字符总数
                double var = pow(sum - avg, 2); // 方差计算
                dp[i][j] = min(dp[i][j], dp[k][j-1] + var); // 状态转移
            }
        }
    }
    
    cout << fixed << setprecision(1) << dp[N][K]/K << endl; // 输出结果，保留1位小数
    return 0;
}

五、总结

1. 算法核心：动态规划通过子问题最优解推导全局最优，结合前缀和降低时间复杂度。

2. 优化点：状态转移方程的三层循环可通过斜率优化等方法进一步提速，但本题数据范围允许朴素DP。

3. 实际应用：适用于需要平衡分组差异的场景，如资源分配、任务调度等。

4. 注意事项：边界条件（如K>N）需提前判断，方差计算需注意浮点数精度。