首页 > 代码库 > uva 1456

uva 1456

2024-07-29 14:45:45   218人阅读

这题说的是 给了 n 个 点 然后每个点 都有 相应的概率，你要将这n个点划分成w个集合使得 下面定义的这种算法 得到的 值最小 n1 是集合一的 个数  $ \pi_{{1}}^{}$是 集合一内的每个点的概率和， 下面是分成两个集合的 样例 前面的系数 是前wi个集合的 总个数

$ \overline{{C}}$ = n1$ \pi_{{1}}^{}$ + (n1 + n2)$ \pi_{{2}}^{}$ = 3(0.3 + 0.05 + 0.1) + (3 + 2)(0.3 + 0.25) = 3 x 0.45 + 5 x 0.55 = 4.1

我们知道肯定不让大概率碰上 大系数 于是我们先对他们进行排序，排完后就得到了我们想要的 

然后dp[j][i] 表示 前j个数分成i个集合的 最小值 

#include <iostream>#include <cstdio>#include <algorithm>#include <string.h>using namespace std;const int maxn=105;double d[maxn];double dp[maxn][maxn];double sum[maxn];int main(){    int cas;    scanf("%d",&cas);    while(cas--){       int n,k;       scanf("%d%d",&n,&k);       double val=0;       for(int i=1; i<=n; ++i){            scanf("%lf",&d[i]);            val+=d[i];        }       for(int i=1; i <= n; ++i)           d[i]/=val;       sort(d+1,d+n+1);       for(int i=1; i<= ( n+1 ) / 2 ; ++i){          double t =d[ i ];          d[ i ]=d[ n - i + 1 ];          d[ n - i + 1 ] = t;       }       sum[0]=0;       for( int i=1; i<=n; ++i)           sum[i]=sum[i-1]+d[i];       for(int i=1;i<=n; ++i){           dp[i][1]=sum[i]*i;       }       for(int i=2; i<=k; ++i)           for(int j=i; j<=n; ++j){                dp[j][i]=105;                for(int e=j; e>=i; e--)                dp[j][i]=min( dp[j][i] , (sum[j]-sum[e-1])*j+dp[e-1][i-1] );             }       printf("%.4lf\n",dp[n][k]);    }    return 0;}
View Code

 

uva 1456


联系
我们