【Codeforces 865C】Gotta Go Fast

二分答案+期望DP

题目大意:

有一个关卡,通关要依次完成 n 个任务,并且完成任务的总时间不超过 R

每个任务有三个数值 ai,bi,pi,表示完成这个任务有 pi% 的概率花费 ai 的时间,1pi% 的概率花费 bi 的时间(ai<bi)。

在任意时刻,可以选择重新开始这个关卡,当前使用的时间清零但通关的总时间不清零。

问通关的期望总时间。

题解:

考虑期望 DP。

f[i][j] 表示剩余的 i+1n 关,到第 i 关已经花费在任务上的时间为 j 时,完成 i+1n 关的期望总时间。

f[i][j]=min

f[0][0] 就是通关的期望总时间。

发现这个式子每次转移的时候都要用到 f[0][0] 的信息,没法直接转移。

我们考虑二分 f[0][0] 的值 k,然后进行上面的DP,转移的时候,f[0][0]k 代替。

最终得到的 f[0][0] 的值可能小于 k。这就说明,实际的期望是小于当前二分的 k 的。如果等于 k,那么说明实际的期望大于等于当前的 k

这里 f 赋初值的时候,都赋为 k,表示不管怎么样,都可以重新开始。

单次 DP 的时间复杂度 O(nR)

Code:

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. using namespace std;
  5. const int N=54;
  6. int n,R,a[N],b[N],m;
  7. double p[N],f[N][N*100+105];
  8. void calc(double _0){
  9. for(int i=0;i<=n;++i)
  10. fill(f[i],f[i]+N*100+104,_0);
  11. for(int i=0;i<=R;++i)f[n][i]=0;
  12. for(int i=n-1;~i;--i)
  13. for(int j=0;j<=R;++j){
  14. f[i][j]=(f[i+1][j+a[i+1]]+a[i+1])*p[i+1]+(f[i+1][j+b[i+1]]+b[i+1])*(1-p[i+1]);
  15. if(f[i][j]>_0)f[i][j]=_0;
  16. }
  17. }
  18. int main(){
  19. cin>>n>>R;
  20. for(int i=1;i<=n;++i)
  21. cin>>a[i]>>b[i]>>p[i],p[i]/=100;
  22. double l=0,r=1e9;
  23. for(int T=128;T--;){
  24. const double mid=(l+r)/2;
  25. calc(mid);
  26. if(f[0][0]<mid)r=mid;else l=mid;
  27. }
  28. printf("%.8f\n",l);
  29. return 0;
  30. }

Gitalking ...