题解：CF167B Wizards and Huge Prize

· · 题解

CF167B 题解（DP, 1800）

（本题解主要是对目前题解区已有做法做了统一的梳理）

题意

给定初始背包容量 k，要进行 n 场比赛，第 i 次胜利的概率为 p_i\times 0.01，失败的概率为 1-p_i\times 0.01，赢的一场比赛能获得一个奖励——当 a_i = -1 时获得一个体积为 1 的奖品，或者当 a_i \gt 0 时给背包增加 a_i 容量，求所有比赛结束后至少赢得 m 场且所有赢得的奖品都能装下的概率。注意，你只需要确保 n 场比赛结束后能装下所有赢得的奖品即可，不需要在获得一件奖品后立刻装下它。

题解

本题非常适合在学习完背包 DP 和简单概率 DP 后进行综合练习，因为其不仅综合了这两个知识点，还搭配上了两个非常较复杂的边界处理。

- $dp_{i+1,j,k}+=dp_{i,j,k}\times (1-p_{i+1})

这个转移有两个问题：

  1. 直接做的状态数是 n\times n\times n^2=n^4 的，会超时；
  2. 由于只要求最终能装下所有赢下的物品，过程中其实是允许背包容量为负的，但目前状态未考虑这些概率。

对于问题一：由于容量最多到 n 就够用了，我们可以把所有 k\ge n 的状态的概率都算到 k=n 的状态里。即将转移式二改为 dp_{i+1,j+1,\min (k+a_{i+1},n)}+=dp_{i,j,k}\times p_{i+1}。

对于问题二，有两个解决的方法：

  1. 转移时，将所有背包放在所有奖品之前，这样再转移的时候，所有背包剩余容量的状态就确实不用考虑了（因为这些状态都对应了装不下奖品的情况）。直接使用上面的转移即可。
  2. 将 k<0 的状态真的引入，发现负数状态依然可以将 k<-n 的状态都算到 k=-n 里，从而 k 需要考虑的范围就是 [-n,n]。代码实现时，可以给 k 这个维度整体偏移 n，将区间移到 [0,2n]。

时间复杂度 O(n^3)。

代码

这里给出对于问题二，使用第一种解决办法的代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<=(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define all(x) (x.begin()),(x.end())
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
struct item{
    int a;
    double p;
}c[210];
bool cmp(item& x,item& y){
    return x.a>y.a;
}
int n,m,k;
double dp[210][210][210];
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    rep(i,1,n){
        cin>>c[i].p;
        c[i].p/=100;
    }
    rep(i,1,n)  cin>>c[i].a;
    sort(c+1,c+1+n,cmp);
    dp[0][0][min(n,k)]=1;
    rep(i,0,n-1){
        rep(j,0,n){
            rep(k,0,n){
                if(k+c[i+1].a>=0)   dp[i+1][j+1][min(k+c[i+1].a,n)]+=c[i+1].p*dp[i][j][k];
                dp[i+1][j][k]+=(1-c[i+1].p)*dp[i][j][k];
            }
        }
    }
    double ans=0;
    rep(j,m,n){
        rep(k,0,n){
            ans+=dp[n][j][k];
        }
    }
    cout<<fixed<<setprecision(8)<<ans<<endl;
    return 0;
}