首先,要把概率从小到大排序,原因很简单,在期望表达式中同样的决策方案人数越多的项占有的比重越小越好;
然后直接dp即可;d[ i ][ j ] 代表到i位置已经分了几组剩下分配的最大期望;
#include <cstdio> #include <map> #include <cmath> #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int inf = 1000; const int maxn = 105; double d[maxn][maxn],w[maxn],sum[maxn]; bool vis[maxn][maxn]; int n,m; double Sum(int x,int y){ return w[y]-w[x-1];} double dp(int i,int j){ if(vis[i][j]) return d[i][j]; vis[i][j] = true; if(i==n&&j<m) return d[i][j]=inf; if(j==m-1){ return d[i][j] = n*Sum(i+1,n); } d[i][j]=inf; for(int k=i+1;k<=n;k++){ d[i][j]=min(d[i][j],dp(k,j+1)+k*Sum(i+1,k)); } return d[i][j]; } int cmp(const double a,const double b){ return a > b; } int main() { int T; scanf("%d",&T); while(T--){ scanf("%d %d",&n,&m); int he=0; for(int i=1;i<=n;i++){ scanf("%lf",&sum[i]); he+=sum[i]; } w[0]=0; for(int i=1;i<=n;i++){ w[i]=sum[i]/he; } sort(w+1,w+n+1,cmp); for(int i=1;i<=n;i++){ w[i]=w[i]+w[i-1]; } memset(vis,false,sizeof(vis)); printf("%.4lf\n",dp(0,0)); } return 0; }