题目大意：
一个游戏关卡有$n(n\le50)$个任务，若在$m$秒内按顺序完成所有任务则算作通过当前关卡。每个关卡有三个属性$a_i,b_i,p_i(1\le a_i<b_i\le100,80\le p_i\le99)$，表示有$p_i\%$的概率用$a_i$秒完成任务$i$，有$1-p_i\%$的概率用$b_i$秒完成任务$i$。每完成一个任务后可以选择继续下一个任务或重新开始当前关卡。问通过当前关卡的期望时间。
思路：
二分答案$k$，并用期望DP进行检验。
用$f[i][j]$表示从第$n$个任务到第$i$个任务，倒计时还剩$j$秒，总时间的期望。
$f[i][j]=(f[i+1][j+a_i]+a_i)p_i+(f[i+1][j+b_i]+b_i)(1-p_i)$。
若$f[i][j]>k$，重新开始当前关卡更优，令$f[i][j]=k$。
则状态转移方程为$f[i][j]=\min((f[i+1][j+a_i]+a_i)p_i+(f[i+1][j+b_i]+b_i)(1-p_i),k)$。
若$f[0][0]<k$，则期望不大于$k$。
1 #include<cstdio> 2 #include<cctype> 3 #include<algorithm> 4 inline int getint() { 5 register char ch; 6 while(!isdigit(ch=getchar())); 7 register int x=ch^\'0\'; 8 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^\'0\'); 9 return x; 10 } 11 const int N=51,M=5001; 12 const double eps=1e-9; 13 int n,m,a[N],b[N],p[N]; 14 double f[N][M]; 15 inline bool check(const double &k) { 16 for(register int i=n-1;~i;i--) { 17 for(register int j=m+1;j<M;j++) f[i+1][j]=k; 18 for(register int j=0;j<=m;j++) { 19 f[i][j]=std::min((f[i+1][j+a[i]]+a[i])*p[i]/100+(f[i+1][j+b[i]]+b[i])*(100-p[i])/100,k); 20 } 21 } 22 return f[0][0]<k; 23 } 24 int main() { 25 n=getint(),m=getint(); 26 for(register int i=0;i<n;i++) { 27 a[i]=getint(),b[i]=getint(),p[i]=getint(); 28 } 29 double l=0,r=1e9; 30 while(r-l>eps) { 31 const double mid=(l+r)/2; 32 (check(mid)?r:l)=mid; 33 } 34 printf("%.10f\n",r); 35 return 0; 36 }
请发表评论