原题链接：鸿雁传书 - 洛谷
? 我不知道这叫背包问题还是区间dp..
? 反正就是顺着来，然后像往常一样的套路。有时候初始化会有点不同还是咋的，记得多想想多试试。?
?注意初始化注意初始化 ！
AC代码：
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define PII pair<int,int>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for(int i = n; i >= 1; ++i)
using namespace std;
const double pi = acos(-1.0);
const int N = 1010;
double a[N], sum[N];
double f[N][110]; 前i个单词分成j段的最小值
int main()
{
int n, k;
cin >> n >> k;
string s;
rep(i, n)
{
cin >> s;
a[i] = s.length();
sum[i] = sum[i - 1] + a[i];
}
double ave = sum[n] / k;
for(int i = 0; i <= n; i++) for(int j = 0; j <= k; j++) f[i][j] = 1e9; //这里两个循环都从0开始，要不然会出问题
f[0][0] = 0; //初始化
for(int i = 1; i <= n; i++)
for(int j = 1; j <= k; j++)
for(int p = 0; p < i; p++) f[i][j] = min(f[i][j], f[p][j - 1] + (sum[i] - sum[p] - ave) * (sum[i] - sum[p] - ave) / k);//p从0开始 因为前i个单词分为1个段的时候是f[0][0] + **
printf("%.1f", f[n][k]);
return 0;
}
?
