题解 | 礼物

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    vector<vector<vector<double>>> dp;
    vector<int> gifts;
    vector<vector<double>> probs;
    int n, m;
    
public:
    double solve(vector<int>& giftCounts, vector<vector<double>>& probabilities) {
        n = probabilities.size() - 1;  // 人数
        m = giftCounts.size() - 1;     // 礼物种类
        gifts = giftCounts;
        probs = probabilities;
        
        // 初始化DP数组
        dp.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            dp[i].resize(m + 1);
            for (int j = 0; j <= m; j++) {
                dp[i][j].resize(gifts[j] + 1, 0.0);
            }
        }
        
        // 设置初始状态
        for (int j = 0; j <= m; j++) {
            dp[0][j][gifts[j]] = 1.0;
        }
        
        // 动态规划过程
        double result = 0.0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k <= gifts[j]; k++) {
                    // 不选择当前礼物
                    dp[i][j][k] = dp[i-1][j][k] * (1 - probs[i][j]);
                    
                    // 选择当前礼物
                    if (k < gifts[j]) {
                        dp[i][j][k] += dp[i-1][j][k+1] * probs[i][j];
                    }
                    if (k == 0) {
                        dp[i][j][k] += dp[i-1][j][0] * probs[i][j];
                    }
                    
                    // 计算最终结果
                    if (i == n) {
                        result += dp[i][j][k] * (gifts[j] - k);
                    }
                }
            }
        }
        
        return result;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> gifts(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> gifts[i];
    }
    
    vector<vector<double>> probs(n + 1, vector<double>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> probs[i][j];
        }
    }
    
    Solution solution;
    cout << fixed << setprecision(1) << solution.solve(gifts, probs) << endl;
    
    return 0;
}

import java.util.*;

class Solution {
    private double[][][] dp;
    private int[] gifts;
    private double[][] probs;
    private int n, m;
    
    public double solve(int[] giftCounts, double[][] probabilities) {
        n = probabilities.length - 1;  // 人数
        m = giftCounts.length - 1;     // 礼物种类
        gifts = giftCounts;
        probs = probabilities;
        
        // 初始化DP数组
        dp = new double[n + 1][m + 1][];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = new double[gifts[j] + 1];
            }
        }
        
        // 设置初始状态
        for (int j = 0; j <= m; j++) {
            dp[0][j][gifts[j]] = 1.0;
        }
        
        // 动态规划过程
        double result = 0.0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k <= gifts[j]; k++) {
                    // 不选择当前礼物
                    dp[i][j][k] = dp[i-1][j][k] * (1 - probs[i][j]);
                    
                    // 选择当前礼物
                    if (k < gifts[j]) {
                        dp[i][j][k] += dp[i-1][j][k+1] * probs[i][j];
                    }
                    if (k == 0) {
                        dp[i][j][k] += dp[i-1][j][0] * probs[i][j];
                    }
                    
                    // 计算最终结果
                    if (i == n) {
                        result += dp[i][j][k] * (gifts[j] - k);
                    }
                }
            }
        }
        
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[] gifts = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            gifts[i] = sc.nextInt();
        }
        
        double[][] probs = new double[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                probs[i][j] = sc.nextDouble();
            }
        }
        
        Solution solution = new Solution();
        System.out.printf("%.1f%n", solution.solve(gifts, probs));
        
        sc.close();
    }
}

class Solution:
    def solve(self, gift_counts: list, probabilities: list) -> float:
        n = len(probabilities) - 1  # 人数
        m = len(gift_counts) - 1    # 礼物种类
        
        # 初始化DP数组
        dp = [[[0.0 for _ in range(gift_counts[j] + 1)] 
              for j in range(m + 1)] 
              for _ in range(n + 1)]
        
        # 设置初始状态
        for j in range(m + 1):
            dp[0][j][gift_counts[j]] = 1.0
        
        # 动态规划过程
        result = 0.0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                for k in range(gift_counts[j] + 1):
                    # 不选择当前礼物
                    dp[i][j][k] = dp[i-1][j][k] * (1 - probabilities[i][j])
                    
                    # 选择当前礼物
                    if k < gift_counts[j]:
                        dp[i][j][k] += dp[i-1][j][k+1] * probabilities[i][j]
                    if k == 0:
                        dp[i][j][k] += dp[i-1][j][0] * probabilities[i][j]
                    
                    # 计算最终结果
                    if i == n:
                        result += dp[i][j][k] * (gift_counts[j] - k)
        
        return result

def main():
    # 读取输入
    n, m = map(int, input().split())
    
    # 读取礼物数量
    gifts = [0] + list(map(int, input().split()))
    
    # 读取概率矩阵
    probs = [[0.0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        row = [0.0] + list(map(float, input().split()))
        for j in range(1, m + 1):
            probs[i][j] = row[j]
    
    # 计算结果
    solution = Solution()
    result = solution.solve(gifts, probs)
    print(f"{result:.1f}")

if __name__ == "__main__":
    main()