XCPC Notes

Appearance

发布时间：2024-07-31

概率期望dp ​

  • 一般情况下，解决概率问题需要顺序循环，而解决期望问题使用逆序循环，如果定义的状态转移方程存在后效性问题，还需要用到高斯消元来优化。

一般情况 ​

有 NN 个数列，第 ii 个数列的中有 PiP_i 个数，分别是 Si,1,Si,2,⋯ ,Si,PiS_{i,1},S_{i,2},\cdots,S_{i,P_i}。

高桥每次可以选一个数列 ii，付出 CiC_i 的代价，得到从 Si,1,Si,2,⋯ ,Si,PiS_{i,1},S_{i,2},\cdots,S_{i,P_i} 中等概率随机的一个数的得分，每次选择时随机抽到哪个数与之前的选择无关。

现在他要得至少 MM 分，每一次他可以根据之前的结果决定选择哪个数列，求他得至少 MM 分需要的最小期望代价。输出与答案的相对误差或绝对误差不超过 10−510^{-5} 则视为正确。

思路：

  • 考虑逆推，$ dp_i表示已经选了i分，还需要m-i分的期望代价，显然dp_m=0 ,答案为dp_0$
  • 易看出dp方程：$ dp_i=c_i+ \sum {j=1}^{P_i} \frac{dp{i+a_j}}{P_i} $
  • $ 注意a_j=0的情况，此时右边式子会出现dp_i要移项到左边，然后再除系数，可以发现此时c_i也带系数了，应该预处理的时候将0处理掉 $
cpp
void solve(){
    int n,m;
    cin>>n>>m;
    vector<double> a[n+1],c(n+1);
    for(int i=1;i<=n;i++){
        cin>>c[i];
        int x;
        cin>>x;
        int cnt=0;
        for(int j=1;j<=x;j++){
            int y;
            cin>>y;
            if(y>0)a[i].push_back(y);
            else cnt++;
        }
        c[i]=c[i]*x/(x-cnt);
    }
    vector<double> dp(m+1,0);
    for(int i=m-1;i>=0;i--){
        double ans=1e18;
        for(int j=1;j<=n;j++){
            double tmp=c[j],cnt=0;
            for(auto x:a[j]){
                cnt+=i+x>=m?0:dp[i+x];
            }
            cnt/=a[j].size();
            tmp+=cnt;
            ans=min(ans,tmp);
        }
        dp[i]=ans;
    }
    cout<<setprecision(5)<<fixed<<dp[0]<<"\n";
}

有后效性情况 ​

高维前缀和(SOSDP) ​

cpp
int n;
pii a[1 << N];

pii merge(pii A, pii B) {
    if(A.fi < B.fi) swap(A, B);
    pii ans = A;
    if(B.fi > ans.se) ans.se = B.fi;
    return ans;
}

void run() {
    for(int i = 0; i < 1 << n; i++) {
        int x; cin >> x;
        a[i] = MP(x, -INF);
    }
    for(int j = 0; j < n; j++) {
        for(int i = 0; i < 1 << n; i++) {
            if(i >> j & 1) a[i] = merge(a[i], a[i ^ (1 << j)]);
        }
    }
    int ans = 0;
    for(int i = 1; i < 1 << n; i++) {
        ans = max(ans, a[i].fi + a[i].se);
        cout << ans << '\n';
    }
}

Wenwei Lin · 2022 — 2025