CF498B题解
2024-10-19 18:26:56
咋黑色啊,这不是看到数据范围就去想 \(O(nT)\) 的做法吗?
然后仔细想想最靠谱的就是 DP。
设 \(dp[n][T]\) 表示听完第 \(n\) 首歌,总共听了 \(T\) 秒。
很明显有 \(dp[n][T]=dp[n-1][T-t_n] \times (1-p)^{t_n}+\sum_{i=1}^{t_n}dp[n-1][T-i] \times (1-p)^{i-1} \times p\)。
很明显这个是 \(O(nT^2)\) 的,接下来开始优化。
我们先先写成 \(dp[n][T]=\sum_{i=1}^{t_n}dp[n-1][T-i] \times (1-p)^{i-1}\),最后令每一项乘上 \(p\)。
发现这个有点儿像把一个长度为 \(t_n\) 的区间当做一个多项式,翻转过来后带入 \(1-p\),我们考虑每次平移一下这个多项式,再去掉多余的项。
然后你发现这个多项式带入后的值其实就是 \(dp[n][T-1]\),所以并不需要新开一个变量。
预处理一下幂就可以做到 \(O(nT)\) 了。
答案为 \(\sum_{i=1}^n\sum_{j=1}^T dp[i][j]\)。
#include<cstdio>
#include<cmath>
typedef long double db;
const int M=5005;
int n,m,t;double p,pw,ans,S[M],dp[2][M];
signed main(){
int i,x;scanf("%d%d",&n,&m);dp[0][0]=1;
for(int T=1;T<=n;++T){
scanf("%d%d",&x,&t);p=.01*x;pw=pow(1-p,t);dp[T&1][0]=0;
for(i=1;i<=m;++i)dp[T&1][i]=dp[T&1][i-1]*(1-p)+dp[T&1^1][i-1],i>t&&(dp[T&1][i]-=dp[T&1^1][i-t-1]*pw);
for(i=1;i<=m;++i)dp[T&1][i]*=p,i>=t&&(dp[T&1][i]+=dp[T&1^1][i-t]*pw),ans+=dp[T&1][i];
}
printf("%.9lf",ans);
}
最新文章
- TJpgDec—轻量级JPEG解码器
- URLDecoder解析url编码
- PDF解析帮助类
- Linux命令--系统中常用的查看命令
- 【问题&;解决】试用版SQL Server 2008 R2 提示评估期已过,数据库不能访问解决办法
- java静态与非静态区别
- 深入理解jQuery的Event机制
- Android L 使用ART能提高多少性能?
- BZOJ_1617_[Usaco2008_Mar]_River_Crossing_渡河问题_(动态规划)
- oracle10 权限角色
- 2018-2019-2 20165231王杨鸿永《网络对抗》Exp1 PC平台逆向破解
- nigix反向代理
- Spring 中StopWatch用法
- 获取修改value
- PAT乙级1027
- 《Science》:对年轻科学家的忠告
- 翻译记忆软件-塔多思TRADO经典教程_4
- k8s内核参数调优
- Drupal7 针对特定条件才显示区块
- 带密匙的php加密解密代码