Acwing 232. 守衛者的挑戰

題意：

有n個挑戰，一開始背包容量為k，每次挑戰有p[i]的概率成功，成功的話會得到一個大小為1的地圖碎片或者是提升背包容量X，所有的地圖碎片必須裝在包里，問最后帶地圖離開的概率

題解：

設f(i,j,k)表示前i個挑戰贏了j次，剩余k次的概率
這么開數組的話會爆炸(200 * 200 * 2000),但是我們知道n個挑戰也就最多只有x個地圖碎片可以拿，那么只要容量大于n就必然成功。所以記f(i,j,n)表示前i個挑戰贏了j次，剩余容量等于n的概率，既然是剩余空間，值域為[-200,200],數組加一個偏移量。這樣就壓縮到O(n³)，就過了。

代碼：

#include<bits/stdc++.h> #define MAXN 205 using namespace std; typedef long long ll; int n,L,k; double f[MAXN][MAXN][MAXN<<1|1],p[MAXN]; int main() {cin>>n>>L>>k;if(k>n)k=n;double ans=0;f[0][0][n+k]=1;for(int i=1;i<=n;++i)scanf("%lf",&p[i]),p[i]/=100;for(int i=1;i<=n;++i){int x;cin>>x;for(int j=0;j<i;++j)for(int k=0;k<=n+n;++k)if(k+x>=0)f[i][j+1][min(n+n,k+x)]+=p[i]*f[i-1][j][k],f[i][j][k]+=(1-p[i])*f[i-1][j][k];}for(int j=L;j<=n;++j)for(int k=n;k<=(MAXN<<1);++k)ans+=f[n][j][k];printf("%.6lf",ans);return 0; }

總結

以上是生活随笔為你收集整理的Acwing 232. 守卫者的挑战的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。