虽然dp方程很好写，就是这个期望不知道怎么求，昨晚的BC也是
题目问题抽象之后为：在一个x坐标轴上有N个点，每个点上有一个概率值，可以修M个工作站，
求怎样安排这M个工作站的位置，使得这N个点都走到工作站的距离期望值最小？
解题报告人：SpringWater(GHQ)
解题思路：状态方程：dp[i][j] = min{ dp[i - 1][k - 1] + cost[k][j] }dp[i][j]表示在1到j修i个站，的最小期望值，
cost【k】【j】是我预处理的k到j这段区间修一个工作站的期望值 ，因为在求cost【k】【j】具
有单调性，所以可以在O（n^2）复杂度算出
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<map>
#define INF ((1<<23)-1)
using namespace std;
map<int ,double> mp;
double f[][];
typedef struct
{
int x; double p;
}Point;
Point pt[];
int kk,m; void initial()
{
for(int i=;i<=;i++)
for(int j=;j<=;j++)
f[i][j]=INF;
for(int i=;i<=m;i++)
for(int j=i;j<=m;j++)
f[i][j]=0.0;
} int main()
{
int k,i,j,l,x; double p;
while( scanf("%d%d",&kk,&m),kk+m )
{
mp.clear();
initial();
for(i=;i<=kk;i++)
{
scanf("%d",&l);
for(j=;j<=l;j++)
{
scanf("%d%lf",&x,&p);
mp[x]+=p;
}
}
map<int,double>::iterator it;
j=;
for( it=mp.begin(); it!=mp.end();it++,j++)
{
pt[j].x=(it->first);
pt[j].p=(it->second);
}
int n=j-;
for( i=;i<=n;i++ )
{
for(j=;j<=m && j<=i; j++ )
{
f[i][j]=INF;
double pre=0.000,suf=0.000;
int cur=i; double add=0.000;
for(k=i-;k>=j-;k--)
{
if( k+ != i )
{
pre+=pt[k+].p;
add+=pt[k+].p*(pt[cur].x-pt[k+].x);
}
while( pt[cur].p+suf < pre )
{
suf+=pt[cur].p;
cur--;
pre-=pt[cur].p;
add-=pt[cur].p*(pt[cur+].x-pt[cur].x);
add+=pt[cur+].p*(pt[cur+].x-pt[cur].x);
add-=pre*(pt[cur+].x-pt[cur].x);
add+=(suf-pt[cur+].p)*(pt[cur+].x-pt[cur].x);
}
f[i][j]=min(f[i][j],f[k][j-]+add);
}
}
}
printf("%.2lf\n",f[n][m]);
}
return ;
}