====== 2020-2021 ICPC Northwestern European Regional Programming Contest (NWERC 2020) ======

[[http://codeforces.com/gym/103049|比赛链接]]

=====  G. Great Expectations =====

==== 题意 ====

有人尝试游戏速通，速通路径理想耗时 $m$，世界记录耗时 $n$。$(m\lt n)$

速通路线上有 $k$ 个难点，从起点达到第 $i$ 个难点需要花费 $t_i$ 时间(假设先前没有失误)。

每个难点有 $p_i$ 概率失误，失误后如果继续游戏需要额外花费 $d_i$，也可以选择立刻从起点重来。问最优策略下打破世界记录的期望时间。

数据保证一局游戏至少有 $\frac 1{50000}$ 的概率打破记录。

==== 题解 ====

设 $\text{dp}(p,t)$ 表示当前刚通过难点 $p$，且剩余容错时间为 $t$ 时，距离打破世界记录还需要花费的时间。于是有状态转移

$$
\text{dp}(p,t) =
t_{i+1}-t_i+p_{i+1}\ast \text{dp}(p+1,t)+(1-p_{i+1})\begin{cases}
\text{dp}(0,n-m-1), & t\lt d_{i+1} \\
\min(\text{dp}(p+1,t-d_{i+1})+d_{i+1},\text{dp}(0,n-m-1)), & t\ge d_{i+1}
\end{cases}
$$

最后题目的答案为 $\text{dp}(0,n-m-1)$，但是求解 $\text{dp}$ 却需要 $\text{dp}(0,n-m-1)$，构成了循环依赖。

考虑二分 $\text{dp}(0,n-m-1)$ 的取值，然后通过 $\text{dp}$ 计算  $\text{dp}'(0,n-m-1)$。

如果 $\text{dp}(0,n-m-1)\lt \text{dp}'(0,n-m-1)$，则说明答案偏小，否则答案偏大。时间复杂度 $O\left(k(n-m)\log \left(\frac {50000n}{\text{eps}}\right)\right)$。

<hidden 查看代码>
<code cpp>
const int MAXN=55,MAXT=5005;
const double eps=1e-6;
double dp[MAXN][MAXT],p[MAXN],ans;
int n,t[MAXN],d[MAXN];
double dfs(int pos,int m){
	if(pos==n)return 0;
	if(dp[pos][m]>0)return dp[pos][m];
	if(m>=d[pos+1])
	dp[pos][m]=t[pos+1]-t[pos]+p[pos+1]*dfs(pos+1,m)+(1-p[pos+1])*min(ans,dfs(pos+1,m-d[pos+1])+d[pos+1]);
	else
	dp[pos][m]=t[pos+1]-t[pos]+p[pos+1]*dfs(pos+1,m)+(1-p[pos+1])*ans;
	return dp[pos][m];	
}
int main()
{
	int t1=read_int(),t2=read_int();
	n=read_int();
	_rep(i,1,n)
	scanf("%d%lf%d",&t[i],&p[i],&d[i]);
	double lef=1,rig=5e4*5e3;
	while(abs(rig-lef)>eps){
		ans=(lef+rig)/2;
		_rep(i,0,n)_rep(j,0,t2-t1)dp[i][j]=-1;
		double res=dfs(0,t2-t1-1);
		if(ans<res)
		lef=ans;
		else
		rig=ans;
	}
	printf("%.7lf",ans+t1-t[n]);
	return 0;
}
</code>
</hidden>