[CF865C] Gotta Go Fast

\(\text{Problem}:\)题目链接

\(\text{Solution}:\)

考虑不存在重开，那么这个游戏的期望时间是确定的。

现在加入重开操作。设答案为 \(X\)，记 \(f(S)\) 表示在某一状态下，达到目的状态花费总的期望时间。如果存在一个非初始状态 \(T\)，使得 \(f(T)>X\)，那么我们可以使用重开操作，使得 \(f(T)=X\)。因为 \(X\) 是最小的期望时间，所以这是可行的。如果对于初始状态 \(P\)，\(f(P)\leq X\),那么在 \(X\) 的期望时间内，可以通过游戏，否则不行。

根据以上的分析。我们可以二分答案 \(X\)，用期望 \(dp\) 来求出 \(f(P)\)。记 \(F_{i,j}\) 表示完成了 \(i+1\) 到 \(n\) 的任务花费了 \(j\) 的时间时，总的期望时间。有转移：

\(F_{i,j}=(F_{i+1,j+a_{i+1}}+a_{i+1})\times \frac{p_{i+1}}{100}+(F_{i+1,j+b_{i+1}}+b_{i+1})\times \frac{100-p_{i+1}}{100}\)

当 \(i>0\) 时，\(F_{i,j}=\min\{F_{i,j},X\}\)。

边界情况也显然，对于 \(0\leq i\leq m\)，\(F_{n,i}=0\)；对于 \(i>m\)，\(F_{n,i}=X\)。

\(F_{0,0}\) 就是 \(f(P)\)。判断一下 \(F_{0,0}\) 与 \(X\) 关系即可。

\(\text{Code}:\)

#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
using namespace std; const int N=52, M=5110;
inline int read()
{
        int s=0, w=1; ri char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
        return s*w;
}
int n,m,a[N],b[N],qz[N],hz[N],p[N];
double F[N][M];
inline bool Check(double X)
{
        for(ri int i=0;i<=qz[n];i++)
        {
                if(i<=m) F[n][i]=0;
                else F[n][i]=X;
        }
        for(ri int i=n-1;~i;i--)
        {
                for(ri int j=qz[i];j>=0;j--)
                {
                        F[i][j]=(F[i+1][j+a[i+1]]+a[i+1])*p[i+1]/100+(F[i+1][j+b[i+1]]+b[i+1])*(100-p[i+1])/100;
                        if(i) F[i][j]=min(F[i][j],X);
                }
        }
        return (F[0][0]<=X);
}
signed main()
{
        n=read(), m=read();
        for(ri int i=1;i<=n;i++) a[i]=read(), b[i]=read(), p[i]=read();
        for(ri int i=1;i<=n;i++) qz[i]=qz[i-1]+b[i], hz[i]=hz[i-1]+a[i];
        double L=1,R=1e9;
        double res=R;
        for(ri int i=1;i<100;i++)
        {
                double mid=(L+R)/2;
                if(Check(mid)) res=mid, R=mid;
                else L=mid;
        }
        printf("%.12lf\n",res);
        return 0;
}