【Codeforces 865C】Gotta Go Fast

mrsrz 11月 27, 2019

二分答案+期望DP

题目大意：

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

每个任务有三个数值 $a_i,b_i,p_i$，表示完成这个任务有 $p_i\%$ 的概率花费 $a_i$ 的时间，$1-p_i\%$ 的概率花费 $b_i$ 的时间（$a_i<b_i$）。

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

问通关的期望总时间。

题解：

考虑期望 DP。

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

$f[i][j]=\min(f[0][0],(f[i+1][j+a_{i+1}]+a_{i+1})\times p_{i+1}\%+(f[i+1][j+b_{i+1}]+b_{i+1})\times (1-p_{i+1}\%))$

$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：

#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;
}