洛谷2112题：用动态规划思想解决字符串分割
2小时前
一、题目解读
洛谷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）需提前判断，方差计算需注意浮点数精度。
原创内容 转载请注明出处
