2024牛客五一集训派对day1 A. Blackjack【概率DP、回滚背包】

A. Blackjack

题目地址

题意

有 $n$ 张牌，每张牌有一个分数 $x_i$，同时给定两个正整数 $a,b$
现在将所有牌随机均匀地打乱，然后从中顺序地抽牌，抽到的牌的分数将累加进得分 $sum$ 中，当得分位于：$[a+1,b]$ 时赢得比赛，若得分 $sum$ 超过 $b$，则输掉比赛。
可以在抽出某张牌后立即停止比赛，当前得分即为最终得分 $sum$
问：如果以最优策略退出，赢得比赛的概率是多少？

数据约定

$1\le n\le 500,1\le a<b\le 500，1\le x_i\le 500$

思路

首先我们需要理解最优策略，也就是当得分 $sum$ 超过 $a$ 时，立即结束游戏，如果此时 $sum\le b$，则获胜，如果不在此时退出，再选额外的牌可能 $sum$ 会超过 $b$；如果此时 $sum>b$，后面也无法力挽狂澜了。

知道这个最优策略后，我们不难想到用背包来统计一些信息：
以 $dp[i][j][sum]$ 表示前 $i$ 个物品，选择了 $j$ 个物品，且分数恰好为 $sum$ 的概率

那么转移为：
$dp[i][j][sum]=dp[i-1][j][sum]+dp[i-1][j-1][sum-w[i]]\times \frac{j}{n-(j-1)}$

第一部分就是直接从前 $i-1$ 个物品转移过来（不取当前 $i$）；第二部分则是先在前 $i-1$ 个物品中取 $j-1$ 个物品，加上当前第 $i$ 个物品的概率，由于已经取走了 $j-1$ 个物品，还剩下 $n-(j-1)$ 个物品，从中取出第 $i$ 个物品概率为：$\frac{1}{n-(j-1)}$，取出第 $i$ 个物品后，它有 $j$ 个位置可以放（已经取出的 $j-1$ 个物品形成了 $j$ 个空位）。

显然这样子的 $dp$ 数组内存占用过大，我们可以采用滚动复用的策略将数组压维到：$dp[j][sum]$，只保留后两维度

然而，此时还不能直接利用 $\forall sum\in [a+1,b]$ 来算 $ans$，因为这样子会算重
考虑 $a=3,b=100$，而 $x_1=2,x_2=3,x_3=50$，显然如果先选了 $x_1$ 和 $x_2$ 后会立即退出游戏，但是如果我们统计 $sum=2+3+50$ 的 $dp[3][sum]$ 的话，我们会在选了 $x_1,x_2$ 的基础上再选上 $x_3$，不符合最优的策略（虽然不会超出 $b$）

那么我们就要考虑枚举最后一个选择的物品 $i$，使得 $sum$ 恰好落在 $[a+1,b]$ 中
如何消除？考虑 回滚背包

我们逆着消除当前物品 $i$ 的贡献，那么此时 $dp$ 数组就只有除了 $i$ 以外的信息了
直接枚举 $sum\in [0,a]$，看看加上 $w[i]$ 是否符合： $sum+w[i]\in [a+1,b]$ 即可，
如果符合，那么以 $i$ 为最后一个选择的贡献就要加上：$dp[j][sum]\times \frac{1}{n-j}$，后面的系数就代表从 $n-j$ 个物品中选出第 $i$ 个物品作为最后一个 的概率（位置唯一，分子为 $1$）

时间复杂度：$O(n^{2}a)$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

const int N = 505;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, a, b;
    std::cin >> n >> a >> b;
    std::vector<int> w(n + 1);
    std::vector<std::vector<double>> dp(n + 1, std::vector<double>(a + 1));
    dp[0][0] = 1;
    fore(i, 1, n + 1){
        std::cin >> w[i]; //分数
        for(int j = n; j >= 1; --j) //枚举已有牌数
            fore(sum, w[i], a + 1) //枚举分数和
                dp[j][sum] += dp[j - 1][sum - w[i]] * j / (n - j + 1);
    }

    double ans = 0;
    fore(i, 1, n + 1){
        std::vector<std::vector<double>> tmp = dp; //回滚背包
        fore(j, 1, n + 1) //消除这张牌的影响
            fore(sum, w[i], a + 1)
                tmp[j][sum] -= tmp[j - 1][sum - w[i]] * j / (n - j + 1);
        
        fore(j, 0, n) //可以不选或选n-1张牌
            fore(sum, 0, a + 1) //选最后这张牌之前，分数和可能为0或恰好为a
                if(sum + w[i] > a && sum + w[i] <= b)
                    ans += tmp[j][sum] / (n - j); //以这张牌作为最后一行获胜牌
    }

    std::cout << std::fixed << std::setprecision(12) << ans;

    return 0;
}