A Dangerous Maze (II)

Dangerous Maze (II)"/>

A Dangerous Maze (II)

题解：期望dp，设正确的门有a个，平均耗时为sum1，错误的门有b个，平均耗时为sum2。
状态转移分2部分：

①当i==k时，即已经记住k次走错的门，
②当i<k时，

#include<bits/stdc++.h>
using namespace std;
const int MX = 105;
double dp[MX];
int x[MX];
int main(){int T,n,k;//  freopen("in.txt","r",stdin);scanf("%d",&T);for(int cas=1;cas<=T;cas++){memset(dp,0,sizeof(dp));scanf("%d%d",&n,&k);int a=0,b;double sum1=0,sum2=0;for(int i=0;i<n;i++) {scanf("%d",&x[i]);if(x[i]>0) {sum1+=x[i];a++;}else sum2+=abs(x[i]);}if(a==0) {printf("Case %d: -1\n",cas);continue;}b=n-a;if(a) sum1/=a;if(b) sum2/=b;k=min(k,b);dp[k]=sum1+(b-k)*sum2/a;for(int i=k-1;i>=0;i--){dp[i]=(dp[i+1]+sum2)*(b-i);dp[i]+=sum1*a;dp[i]/=n-i;}printf("Case %d: %.7f\n",cas,dp[0]);}return 0;
}