LA 4731 Cellular Network（贪心+概率+dp）

柔情只为你懂 2021-12-12 17:59 81阅读 0赞

## 题意： 存在一个蜂窝网络，有n个部分，有一部手机存在着n个部分中的某一个，给定每个部分的存在概率，现在要将这n个部分分成w块，每一块内的部分同时访问。让你完成划分并输出找到手机的最小访问块数期望。 ##

## 分析： 显然先访问大概率的部分，使期望最小。先将n部分按概率从大到小排序，每次划分块时选择连续的一段。dp\[i\]\[j\]为前i部分划分成j块的最小期望，有如下转移： ##

## dp\[i\]\[j\] = min(dp\[i\]\[j\], dp\[k\]\[j-1\] + 第k+1块到第i块有手机的概率\*i块)。O（n^3）。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    int T,n,w,u[110];
    int dp[110][110],p[110],s[110];
    
    bool cmp(int a,int b) {
        return a>b;
    }
    
    int main() {
        scanf("%d",&T);
        while(T--) {
            scanf("%d%d",&n,&w);
            int sum=0;
            for(int i=1;i<=n;i++) {
                scanf("%d",&p[i]);
                sum+=p[i];
            }
            sort(p+1,p+1+n,cmp);
            for(int i=1;i<=n;i++)
                s[i]=s[i-1]+p[i];
            memset(dp,inf,sizeof(dp));
            dp[0][0]=0;
            for(int i=1;i<=n;i++) {
                for(int j=1;j<=w;j++) {
                    for(int k=j-1;k<i;k++) {
                        dp[i][j]=min(dp[i][j],dp[k][j-1]+i*(s[i]-s[k]));
                    }
                }
            }
            printf("%.4f\n",1.0*dp[n][w]/sum);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，81人围观）

还没有评论，来说两句吧...

相关阅读

相关概率期望dp

简易的入门：http://kicd.blog.163.com/blog/static/126961911200910168335852/ 大神的总结：http://blog

港控/mmm°/ 2023年08月17日 16:25/ 0 赞/ 116 阅读

相关烟花（概率dp）

https://ac.nowcoder.com/acm/problem/18200 分析： double x = 1.0000 - arr\[i\]; doubl

秒速五厘米/ 2023年01月13日 15:56/ 0 赞/ 220 阅读

相关算法提高概率计算（概率dp）

问题描述　　生成n个∈\[a,b\]的随机整数，输出它们的和为x的概率。输入格式　　一行输入四个整数依次为n，a，b，x，用空格分隔。输出格式　　输出一行包

缺乏、安全感/ 2022年09月28日 15:20/ 0 赞/ 213 阅读

相关 HDU Walk （概率DP）

HDU Walk （概率DP）：[http://acm.hdu.edu.cn/showproblem.php?pid=5001][http_acm.hdu.edu.cn_sho

柔光的暖阳◎/ 2022年08月21日 11:58/ 0 赞/ 201 阅读

相关 hdu 4586 概率dp

题意：扔一个有n面的骰子，可能得到正面朝上的那个面上面的数字，有一些面比较特殊，扔到这些面上之后可能继续扔，问最终能等到的数字和的期望。分析：这道题

灰太狼/ 2022年08月20日 15:21/ 0 赞/ 187 阅读

相关 Corporative Network LA3027

include <stdio.h> include <string.h> include <algorithm> include <math.h

我不是女神ヾ/ 2022年08月07日 05:42/ 0 赞/ 3 阅读

相关 lightoj 1030 概率dp

1030 - Discovering Gold <table> <tbody> <tr> <td title="special judge"><a href

超、凢脫俗/ 2022年07月28日 04:10/ 0 赞/ 234 阅读

相关 BZOJ3566 概率充电器树形概率dp

[传送门][Link 1] 题意：给你一棵树，求能充电节点的期望个数，每条边都有一个概率，每个点也有一个概率。思路：从反面考虑：设s\[u\]是u没电，以及它的孩

不念不忘少年蓝@/ 2022年05月15日 08:00/ 0 赞/ 232 阅读

相关 LA 4731 Cellular Network（贪心+概率+dp）

题意：存在一个蜂窝网络，有n个部分，有一部手机存在着n个部分中的某一个，给定每个部分的存在概率，现在要将这n个部分分成w块，每一块内的部分同时访问。让你完成划分并输出找到手

柔情只为你懂/ 2021年12月12日 17:59/ 0 赞/ 82 阅读

相关 LA4987 EvacuationPlan 疏散计划（dp+贪心）

题意：n个施工队，m个避难所，在一个正x坐标轴上，给出每个施工队坐标和每个避难所坐标，要求每个施工队到一个避难所避难，且每个避难所至少有一个施工队，求所有施工队所走的距离和的

野性酷女/ 2021年11月17日 02:52/ 0 赞/ 152 阅读