【CF865C】Gotta Go Fast 二分+期望DP

【CF865C】Gotta Go Fast

题意：有n个关卡需要依次通过，第i关有pi的概率要花ai时间通过，有1-pi的概率要花bi时间通过，你的目标是花费不超过m的时间通关，每一关开始时你都可以选择进行这个关卡或是重新开始。问你达成目标的最短期望总时间（假设你是绝顶聪明的）。

n<=50,m<=5000。

题解：设f[i][j]表示已经完成了前i关，用了j的时间，期望的通关最小总时间。那么每一关开始时你都可以选择打或不打，所以得到DP方程：

f[i-1][j]=min(f[0][0],(f[j+ai]+ai)*pi+(f[j+bi]+bi)*(1-pi))

但是问题来了，我们现在还不知道f[0][0]的值，怎么办？

我们可以二分！容易发现，当我们假定的f[0][0]比真正值大时，算出来的f[0][0]要比假定值小，反之比假定值大。这个原理感觉和分数规划的思想差不多。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
double f[55][5110];
int n,m;
int a[55],b[55];
double p[55];
bool check(double mid)
{
        int i,j;
        for(i=0;i<=n;i++)    for(j=0;j<=m+100;j++)        f[i][j]=mid;
        for(j=0;j<=m;j++)    f[n][j]=0;
        for(i=n;i>=1;i--)
        {
                for(j=0;j<=m;j++)
                {
                        f[i-1][j]=min(mid,(f[i][j+a[i]]+a[i])*p[i]+(f[i][j+b[i]]+b[i])*(1-p[i]));
                }
        }
        return f[0][0]<mid;
}
inline int rd()
{
        int ret=0,f=1;  char gc=getchar();
        while(gc<\'0\'||gc>\'9\') {if(gc==\'-\')  f=-f;   gc=getchar();}
        while(gc>=\'0\'&&gc<=\'9\')       ret=ret*10+(gc^\'0\'),gc=getchar();
        return ret*f;
}
int main()
{
        n=rd(),m=rd();
        int i;
        double l=0,r=34751706,mid;
        for(i=1;i<=n;i++)    a[i]=rd(),b[i]=rd(),p[i]=rd()*0.01;
        for(i=1;i<=60;i++)
        {
                mid=(l+r)/2;
                if(check(mid))  r=mid;
                else    l=mid;
        }
        printf("%.9f",r);
        return 0;
}