根据排序不等式可知，逆序和最小（就是两个向量坐标一个递增一个递减，那么乘起来就最小）
所以排一下序，然后做一下线性dp即可
#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#define MAXN 105#define ll long longusing namespace std;double f[MAXN][MAXN];int n,m;double c[MAXN];double s[MAXN];int a[MAXN];int sum;bool comp(const int &p1,const int &p2){ ???return (p1>p2); ???}void solve(){ ???scanf("%d%d",&n,&m); ???sum=0; ???for(int i=1;i<=n;i++){ ???????scanf("%d",&a[i]); ???????sum+=a[i]; ???} ???sort(a+1,a+n+1,comp); ???for(int i=1;i<=n;i++){ ???????c[i]=1.0*a[i]/sum; ???????s[i]=s[i-1]+c[i]; ???} ???for(int i=1;i<=n;i++){ ???????f[i][1]=i*s[i]; ???????for(int j=2;j<=m;j++){ ???????????f[i][j]=100000000000; ???????????for(int k=j-1;k<i;k++){ ???????????????f[i][j]=min(f[i][j],f[k][j-1]+(s[i]-s[k])*i); ???????????} ???????} ???} ???printf("%.4f\n",f[n][m]);}int main(){// ???freopen("data.in","r",stdin); ???int T; ???scanf("%d",&T); ???while(T--){ ???????solve(); ???} ???return 0;}UVA4731：Cellular Network
原文地址：http://www.cnblogs.com/w-h-h/p/7854544.html