【Codeforces 865C】Gotta Go Fast
二分答案+期望DP
题目大意:
有一个关卡,通关要依次完成 n 个任务,并且完成任务的总时间不超过 R。
每个任务有三个数值 ai,bi,pi,表示完成这个任务有 pi% 的概率花费 ai 的时间,1−pi% 的概率花费 bi 的时间(ai<bi)。
在任意时刻,可以选择重新开始这个关卡,当前使用的时间清零但通关的总时间不清零。
问通关的期望总时间。
题解:
考虑期望 DP。
令 f[i][j] 表示剩余的 i+1∼n 关,到第 i 关已经花费在任务上的时间为 j 时,完成 i+1∼n 关的期望总时间。
f[i][j]=minf[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:
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=54;
int n,R,a[N],b[N],m;
double p[N],f[N][N*100+105];
void calc(double _0){
for(int i=0;i<=n;++i)
fill(f[i],f[i]+N*100+104,_0);
for(int i=0;i<=R;++i)f[n][i]=0;
for(int i=n-1;~i;--i)
for(int j=0;j<=R;++j){
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]);
if(f[i][j]>_0)f[i][j]=_0;
}
}
int main(){
cin>>n>>R;
for(int i=1;i<=n;++i)
cin>>a[i]>>b[i]>>p[i],p[i]/=100;
double l=0,r=1e9;
for(int T=128;T--;){
const double mid=(l+r)/2;
calc(mid);
if(f[0][0]<mid)r=mid;else l=mid;
}
printf("%.8f\n",l);
return 0;
}
Gitalking ...