bzoj 3029 守卫者的挑战 —— 概率DP
2024-09-29 11:50:32
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3029
设 f[i][j][k] 表示第 i 次挑战,已经成功 j 次,剩余容量为 k 的概率;
体积大于2000的按2001计算即可,反正也用不完,否则开不下。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=,maxm=;
int n,l,m,a[maxn];
double p[maxn],f[maxn][maxm],ans;
int main()
{
scanf("%d%d%d",&n,&l,&m);
for(int i=;i<=n;i++)scanf("%lf",&p[i]),p[i]/=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>)a[i]=;
}
f[][m+]=;
for(int i=;i<=n;i++)
for(int j=i;j>=;j--)
for(int k=maxm-;k>=;k--)
{
f[j][k]=f[j][k]*(1.0-p[i]);
if(j&&k>=a[i])f[j][k]+=f[j-][k-a[i]]*p[i];
}
for(int j=l;j<=n;j++)
for(int k=;k<=maxm;k++)ans+=f[j][k];
printf("%.6lf\n",ans);
return ;
}
最新文章
- RequireJS 模块的定义与加载
- css 隔行变色,表单布局
- 【原创】js实现一个可随意拖拽排序的菜单导航栏
- CSS 派生选择器
- Java Servlet 工作原理问答
- Mac下安装MySQL-python
- php之类,对象(四)加载类及练习题
- Ubuntu升级后apache所有的失败,以解决虚拟文件夹的设置
- 应用Git Flow—Git团队协作最佳实践
- JS基础速成(二)-BOM(浏览器对象模型)
- Html元素添加事件禁用
- 032、学容器必须懂bridge网络(2019-02-19 周二)
- 潭州课堂25班:Ph201805201 django框架 第六课 模型类增删改查,常用 的查询矣查询条件 (课堂笔记)
- selenium_unittest基本框架
- 另开一篇 https
- WPF定义样式文件的方式
- Python3.x(windows系统)安装requests库
- IBM V7000错误代码及解决
- jenkins + k8s + lnp
- Python将科学计数法数值转换为指定精度浮点数