设为首页 加入收藏

TOP

hdu4921 Map
2015-07-20 17:57:23 来源: 作者: 【大 中 小】 浏览:1次
Tags：hdu4921 Map

给最多10条链，每条链长度最大1000，链上每点有权值，每条链上按顺序，第i个点属于level[i]，

链上后一个点可以选的前提是前面的点都选了。

选择了一些点可以得到的分数是两部分加起来：1、全部点权和 2、leveli的点共有yi个，若你选择了xi个，则得分：你选择的该层点权和*xi/yi

问所有可能的取值组合的分数期望。


题意太纠结了，读的好心塞，感觉思考能力都下降了。


因为题目是求期望，所以我们需要得到，1、总方案数，2、所有取法的得分和。

对于1，就是（每条链上点数+1）相乘-1就是了

对于问题2，

其中主要要解决得分规则2，由于总共最多10条链，对于每一个level i ，我们可以想到用二进制记录第i层状态，枚举第i层的取法，

这样我们的问题就变成了，我们要求每一种取法的得分数，以及在总方案数中，这种取法占了多少种。

这样还是比较好算的，假如第i层，有第1 3 4 6条链上可以取，你取了1 3上的第i个数，则第4 6条链最多取到第i-1个数，假设第1 3 4 6条链上总共分别有5 6 3 4个点，

那么取1 3的全部方案数就是 （5-1）×（6-3）×min(3,i)×min(4,i) 种，因为1 3链上必须取到第i个数，第i个后面的可选，而第4 6条链只能选前i-1个数，那么这样乘起来就是总方案数。

现在主要问题都解决了，我们就可以累加得分算出总得分，进而求期望了。

题目的wa点有：点从0开始记数，总方案数用int会爆，直接double就可以了。



#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
        using namespace std; const int maxn=10010; int vis[maxn],son[maxn],len[15],val[maxn],level[maxn],mk[maxn],list[15][1005]; double cal(int a,int b)//a表示枚举到第alevel b的二进制位表示levela层可能取哪些链 { double n=1,sum=0; int cnt=0; for(int i=1;i<=10;i++,b>>=1) { if(b&1) { cnt++; n*=(len[i]-a); sum+=list[i][a]; } else n*=(min(len[i],a)+1); } return sum*((cnt>1?cnt:0)+level[a])/level[a]*n; } int main() { int icy,m,i,n,k,j,a,b; scanf("%d",&icy); while(icy--) { scanf("%d%d",&n,&m); for(i=0;i
        
         0;j=(j-1)&mk[i])//枚举这一层取哪几条链上的所有可能 sum+=cal(i,j); printf("%.3lf\n",sum/tot); } return 0; }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：poj 3258(二分) 下一篇：poj 3273（原来以为是dp呢，居然..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: