自动搬运

查看原文

来自洛谷，原作者为

	KillerXu OI和文化课都很菜的选手

搬运于2025-08-24 21:34:08，当前版本为作者最后更新于2019-02-18 21:46:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

既然不能把情书中的单词拆开，那么每个单词就是独立的，我们只要去探究每个单词的长度，换行我们直接理解为分段就可以了。

于是题意其实就是给出一个有$n$个数的数列，将这个数列分成$k$段，使每一段所有数的总和方差最小。

这道题我们考虑dp，显然我们的子问题就是把前$i$个数分成$j$段，每一段所有数的总和方差最小，状态应由$i$前面所有的数分成$j-1$段的最好结果转移过来。

可以写出转移方程了：

设$f[i][j]$表示前$i$个数分成$j$段，最小的每一段所有数总和的方差。

$f[i][j]=min(f[i][j],f[l][j-1]+sum(i,l))$

其中$1≤l≤i-1$,$sum(i,l)$表示从$i$到$l$这一段数的和减去平均数的平方再除以$k$，实际操作时可以用前缀和。答案最后在$f[n][k]$里。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 1005
#define MAXK 105
using namespace std;
int n,k;
double a[MAXN],f[MAXN][MAXK];//a[i]表示第i个单词的长度 
double s[MAXN];//s是前缀和数组 
int main(){
	scanf("%d%d",&n,&k);
	double ave=0;//记录平均数 
	for(int i=1;i<=n;i++){
		char str[25];
		scanf("%s",str);//读入单词（全是x） 
		a[i]=strlen(str);//记录单词长度 
		ave+=a[i];//累加起来好算平均数 
		s[i]=s[i-1]+a[i];//计算前缀和 
	}
	ave/=k;//算出平均数
	
	for(int i=1;i<=n;i++)
	 for(int j=2;j<=k;j++)
	  f[i][j]=0x7fffffff;//除了第一列，其他地方都初始化成最大值 
	  for(int i=1;i<=n;i++) f[i][1]=(s[i]-ave)*(s[i]-ave)/k;//分成一段的最小值直接计算出方差就行了 
	  
	for(int j=2;j<=k;j++)//分成一段不用处理了，直接从分成两段开始处理 
	 for(int i=j;i<=n;i++)//前面i个数最多也只能分成i段，所以如果j>i就不行 
	  for(int l=1;l<=i-1;l++) 
	   f[i][j]=min(f[i][j],f[l][j-1]+(s[i]-s[l]-ave)*(s[i]-s[l]-ave)/k);//转移方程 
	   
	    printf("%.1lf",f[n][k]);//输出即可 
	  
	   return 0;
}