LightOJ - 1395 迷宫问题进阶版

题目链接：
题目大意：这题是Light Oj 1027的加强版,1027那道是无记忆的：https://blog.csdn.net/qq_21433411/article/details/89842819。
题意： 有n扇门，每次你可以选择其中一扇。xi为负值的门带你abs(xi)后又回到原点。xi为正值
的门则带你离开迷宫，并且你会记住你前面选择的K道门，在下次选择的时候不会选择这些门。选择每扇门的概率相等。求走出迷宫的时间期望值。

思路：如果k=0就是上面那道题。如果k！=0，我们知道前面k道门一定是xi<0的。那么我们可选择的门和k相关。

#include<bits/stdc++.h>
#define LL long long
#define DB double
using namespace std;

DB f[105];
int main(){

    int T, cas=1; scanf("%d", &T);
    while(T--){
        int n, k, x; scanf("%d%d", &n, &k);
        int n1=0, n2=0, sum1=0, sum2=0;
        for(int i=1; i<=n; i++){
            scanf("%d", &x);
            if(x>0){
                n1++; sum1+=x;
            }
            else{
                n2++, sum2+=-x;
            }
        }
        if(!n1){
            printf("Case %d: -1\n", cas++);
            continue;
        }
        k=min(n2, k);
        DB s2;
        if(n2){
            s2=sum2*1.0/n2;
        }
        else{
            s2=0;
        }

        f[k]=(sum1+s2*(n2-k))*1.0/(n-n2);
        for(int i=k-1; i>=0; i--){
            f[i]=sum1*1.0/(n-i)+((n2-i)*(f[i+1]+s2))/(n-i);
        }
        printf("Case %d: %.8f\n", cas++, f[0]);
    }

    return 0;
}