二十九 4009. 收集卡牌 (数学期望|状压DP)

4009. 收集卡牌 (数学期望|状压DP)

略

import java.util.*;

public class Main {
    private static final int N = 16, M = 1 << N;
    private static int n, m;
    private static double[] p = new double[N];
    private static double[][] dp = new double[M][N * 5 + 1];
    
    private static double f(int state, int coins, int r) {
        if (dp[state][coins] >= 0) {
            return dp[state][coins];
        }
        if (coins >= r * m) {
            return dp[state][coins] = 0;
        }
        
        dp[state][coins] = 0;
        for (int i = 0; i < n; i++) {
            if (((state >> i) & 1) != 0) {
                dp[state][coins] += p[i] * (f(state, coins + 1, r) + 1);
            }
            else {
                dp[state][coins] += p[i] * (f(state | (1 << i), coins, r - 1) + 1);
            }
        }
        return dp[state][coins];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextDouble();
        }
        for (int i = 0; i < M; i++) {
            Arrays.fill(dp[i], -1);
        }
        System.out.println(String.format("%.10f", f(0, 0, n)));
    }
}