概率 dp lightoj 1395
2024-10-08 11:45:32
dp[k]用类似于低配版的这道题的做法求出,如下;
然后就从k逆推到0就好了
#include<bits/stdc++.h>
using namespace std;
const int MX = ;
double dp[MX];
int x[MX];
int main(){
int T,n,k;
scanf("%d",&T);
for(int cas=;cas<=T;cas++){
memset(dp,,sizeof(dp));
scanf("%d%d",&n,&k);
int a=,b;
double sum1=,sum2=;
for(int i=;i<n;i++) {
scanf("%d",&x[i]);
if(x[i]>) {sum1+=x[i];a++;}
else sum2+=abs(x[i]);
}
if(a==){
printf("Case %d: -1\n",cas);
continue;
}
b=n-a;
if(a) sum1/=a;
if(b) sum2/=b;
k=min(k,b);
dp[k]=sum1+(b-k)*sum2/a;
for(int i=k-;i>=;i--){
dp[i]=(dp[i+]+sum2)*(b-i);
dp[i]+=sum1*a;
dp[i]/=n-i;
}
printf("Case %d: %.7f\n",cas,dp[]);
}
return ;
}
最新文章
- C++迪杰斯特拉算法求最短路径
- Tomcat启动后,从spring容器中获取Bean和ServletContext
- 20145218&;20145240 《信息安全系统设计基础》实验三 实时系统的移植
- android QQ消息左滑动删除实例(优化版SwipeListViewEX)
- html基础总结版
- 你会用Python做出装逼的东西吗
- 准备在新项目中使用pgsql【资源收集】
- 练习2 G题 - 数值统计
- [Struts2学习笔记] -- 输入校验
- python 函数形参四种格式
- CodeForces 610B Vika and Squares
- Ambari2.5.3卸载smartsense
- ES6中的类
- 初识Http协议抓包工具—Fiddler
- Guava常用方法
- http_server.go
- RecyclerView实现一个页面有多种item,每个item有多个view,并且可以让任意item的任意view自定义监听,通过接口方法进行触发操作
- 剑指offer:1.找出数组中重复的数(java版)
- js中字符替换函数String.replace()使用技巧
- vs widows服务的开发