Wannafly挑战赛8 - C.小C打比赛

2023-11-06 23:38
文章标签 比赛 挑战赛 wannafly

本文主要是介绍Wannafly挑战赛8 - C.小C打比赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:https://www.nowcoder.com/acm/contest/57/C

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述 

小C现在要参加一场wannafly挑战赛,一场挑战赛一共有n道题,一共有m分钟。
对于第i道题,小C解决它需要恰好j分钟的概率是p i,j
小C每次会选择某一道没做完的题,然后把它解决(不能中途放弃),之后再决策下一道要做的题是哪道。
求小C在最优策略下,期望能做出几道题。

输入描述:

第一行两个正整数n,m
接下来一共n行,每行有m个小数,第i行的第j个小数表示pi,j(这里假设不存在0分钟A题的dalao)。

输出描述:

输出一个小数,表示期望能做出几道题,保留小数点后五位。
示例1

输入

2 5
0.2 0.2 0.2 0.2 0.2
0 0.25 0.25 0.25 0.25

输出

1.30000

备注:

1≤ n≤ 6,1≤ m≤ 180
每道题的概率和为1(每道题只要时间够一定能做出来)
输入最多四位小数

代码:

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<set>
#include<iomanip>
using namespace std;
int n,m;
double a[9][209],dp[109][209];
int main()
{scanf("%d%d",&n,&m);int i,j,k,l;double tmp;for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%lf",&a[i][j]);for(i=1;i<(1<<n);i++) //枚举不同选择方案for(j=1;j<=m;j++)     //枚举花费时间{for(k=1;k<=n;k++) //当前这种方案i都是用了哪道题if(i&(1<<(k-1)))  //用了题目k{for(l=1,tmp=0;l<=j;l++)     //用l分钟做k题目tmp+=(1+dp[i^(1<<(k-1))][j-l])*a[k][l]; //i^(1<<k-1)即未选k时的方案,这里dp[i][j]计算的是期望dp[i][j]=max(dp[i][j],tmp);}}printf("%.5f\n",dp[(1<<n)-1][m]);return 0;
}


这篇关于Wannafly挑战赛8 - C.小C打比赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/359762

相关文章

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期(金牌),从过程而言和我的预期相差甚远(打的太乱,个人发挥很差),还好关键时刻队友抗住压力,负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的,先把A,B,C草草水过(A题小写x打成大写的也是醉了),我和老高开始各种测机器,long long不出所料是lld的,试了一下除0和数组越界的re问题,发现没有re,只有wa(甚至数组越界还AC了),至于栈深的话也没过多追

ACM比赛中如何加速c++的输入输出?如何使cin速度与scanf速度相当?什么是最快的输入输出方法?

在竞赛中,遇到大数据时,往往读文件成了程序运行速度的瓶颈,需要更快的读取方式。相信几乎所有的C++学习者都在cin机器缓慢的速度上栽过跟头,于是从此以后发誓不用cin读数据。还有人说Pascal的read语句的速度是C/C++中scanf比不上的,C++选手只能干着急。难道C++真的低Pascal一等吗?答案是不言而喻的。一个进阶的方法是把数据一下子读进来,然后再转化字符串,这种方法传说中

结合Python与GUI实现比赛预测与游戏数据分析

在现代软件开发中,用户界面设计和数据处理紧密结合,以提升用户体验和功能性。本篇博客将基于Python代码和相关数据分析进行讨论,尤其是如何通过PyQt5等图形界面库实现交互式功能。同时,我们将探讨如何通过嵌入式预测模型为用户提供赛果预测服务。 本文的主要内容包括: 基于PyQt5的图形用户界面设计。结合数据进行比赛预测。文件处理和数据分析流程。 1. PyQt5 图形用户界面设计

保研 比赛 利器: 用AI比赛助手降维打击数学建模

数学建模作为一个热门但又具有挑战性的赛道,在保研、学分加分、简历增色等方面具有独特优势。近年来,随着AI技术的发展,特别是像GPT-4模型的应用,数学建模的比赛变得不再那么“艰深”。通过利用AI比赛助手,不仅可以大大提升团队效率,还能有效提高比赛获奖几率。本文将详细介绍如何通过AI比赛助手完成数学建模比赛,并结合实例展示其强大功能。 一、AI比赛助手的引入 1. 什么是AI比赛助手? AI比

Kaggle刷比赛的利器,LR,LGBM,XGBoost,Keras

刷比赛利器,感谢分享的人。 摘要 最近打各种比赛,在这里分享一些General Model,稍微改改就能用的 环境: python 3.5.2 XGBoost调参大全: http://blog.csdn.net/han_xiaoyang/article/details/52665396 XGBoost 官方API: http://xgboost.readthedocs.io/en

【HDU】1285 确定比赛名次 拓扑排序

确定比赛名次 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10963    Accepted Submission(s): 4374 Problem Description 有N个比赛队(1<=N<=500),

2024年第十届数维杯国际大学生数学建模挑战赛

竞赛介绍 为了培养学生的创新意识及运用数学方法和计算机技术解决实际问题的能力,内蒙古创新教育学会、内蒙古基础教育研究院决定主办2024年第十届数维杯国际大学生数学建模挑战赛(国际赛)。 数维杯大学生数学建模挑战赛每年分为两场,每年上半年为数维杯国赛(5月,俗称小国赛),下半年为数维杯国际赛(11月),2023年数维杯国际大学生数学建模挑战赛共有近1.5万名学生参赛,参赛队伍来自国内外1177所

第八届湘潭大学程序设计比赛A题

A Love Letter Accepted : 33 Submit : 66Time Limit : 1000 MS Memory Limit : 65536 KB  题目描述   CodeMonkey终于下定决心用情书的方式向心爱的女神表白,当他历经几天几夜写完之后才知道女神有很多不喜欢的词,所以他不得不有把这些词删掉。例如:原文是:ILOVEYOU,女神不喜欢的词是‘LV’

高校计算机能力挑战赛C++

2020 1.Excel表列名称由字母A~Z组成,列字母的规律如下: A、B、C.....Z、AA、AB......AZ、BA、BB.......ZZZZY、ZZZZZ....... 输入:输入包含两个列名称字符串,长度均小于等于5。输出: 输出:两个列名称之间共有多少列 样例输入: AA  AZ 样例输出: 24 2."九键拼音中数字与英文字母成对应关系:2--abc, 3-def,

2020计算机挑战赛Java组真题

单选题 1.下列叙述哪些是错误的(). A.final 类不可以有子类 B.构造方法是类的一种特殊方法,其方法名必须与类名相同 C.抽象类可以用new运算符创建对象 D.内存回收程序不允许程序员直接释放内存2.下列叙述哪些是错误的(). A.abstract类不可以用new和构造函数定义对象 B.构造方法的返回值类型只能是void型 C.内存回收程序负责释放无用内存 D.Java类只能是单继承的