题解 P2112 【鸿雁传书】

· · 题解

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

于是题意其实就是给出一个有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;
}