题意：一共有n个关卡，需要顺次完成。通过第i个关卡需要Fi秒有Pi的概率，需要Si秒有1-Pi的概率。限制在R秒内一次性通过n个关卡。如果时间超了，可以选择重置，即从第1关重新开始打。
问期望通关所需的总时间？
标程：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const double eps=1e-9; 5 const int N=55; 6 int n,r,f[N],s[N],p[N]; 7 double L,R,dp[N][N*100],t; 8 bool check(double x) 9 { 10 for (int i=n;i>=1;i--) 11 { 12 for (int j=r+1;j<=5100;j++) dp[i+1][j]=x; 13 for (int j=0;j<=r;j++) 14 dp[i][j]=min(x,p[i]/100.0*(dp[i+1][j+f[i]]+f[i])+(1-p[i]/100.0)*(dp[i+1][j+s[i]]+s[i])); 15 } 16 return dp[1][0]<x; 17 } 18 int main() 19 { 20 scanf("%d%d",&n,&r); 21 for (int i=1;i<=n;i++) scanf("%d%d%d",&f[i],&s[i],&p[i]); 22 L=0;R=1e9; 23 for (int i=1;i<=100;i++) 24 { 25 double mid=(L+R)/2.0; 26 if (check(mid)) R=mid;else L=mid; 27 } 28 printf("%.10lg\n",L); 29 return 0; 30 }
易错点：1.注意二分100次就够了。不然会被卡时间。
2.贪心的策略，只有当时间超限， 才选择重置。也就是说只有玩到超时（是要加上最后那一次超时关卡的时间的），才放弃继续的希望。
题解：二分答案+概率dp
重置是一个有趣的操作，重置以后到通关的时间也就是我们dp中要求的通关期望时间。
一开始我们还不知道怎么办？二分答案吧。
设mid为期望通关时间。dp[i][j]表示现在在第i关，这一关之前已经花了j的时间（不算上重置）=从这里到通关的期望时间。
1.Fi：dp[i][j]<-(dp[i+1][j+Fi]+Fi)*Pi
2.Si: dp[i][j]<-(dp[i+1][j+Si]+Si)*(1-Pi)
3.发现j+Fi>=R或j+Si>=R（有希望一定要先试一下），出界则重置，
dp[i][j]<-(mid+Fi)*Pi或dp[i][j]<-(mid+Si)*(1-Pi)。
4.发现玩这一关期望通关时间比重置还长，没希望了直接重置，dp[i][j]=min(mid,dp[i][j])。
