[BZOJ 3029]守卫者的挑战：期望DP

本文主要是介绍[BZOJ 3029]守卫者的挑战：期望DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

f[i][j][k]表示前i个挑战中挑战成功j次，目前背包容量-碎片数为k的概率。
直接开这么大的数组会MLE，因此需要使用滚动数组。

/*
User:Small
Language:C++
Problem No.:3029
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=2e2+5;
double p[M],f[3][M][M*2],ans;
int n,l,t,d[M],a,b;
int main(){freopen("data.in","r",stdin);//scanf("%d%d%d",&n,&l,&t);for(int i=1;i<=n;i++){scanf("%lf",&p[i]);p[i]/=100;}for(int i=1;i<=n;i++)scanf("%d",&d[i]);if(t>n) t=n;f[0][0][t+200]=1;a=0,b=1;for(int i=0;i<n;i++){memset(f[b],0,sizeof(f[b]));for(int j=0;j<=n;j++){for(int k=-n;k<=n;k++){if(f[a][j][k+200]==0) continue;f[b][j+1][min(k+d[i+1],n)+200]+=f[a][j][k+200]*p[i+1];f[b][j][k+200]+=f[a][j][k+200]*(1-p[i+1]);}}swap(a,b);}for(int i=l;i<=n;i++)for(int j=0;j<=n;j++) ans+=f[a][i][j+200];printf("%.6lf\n",ans);return 0;
}

这篇关于[BZOJ 3029]守卫者的挑战：期望DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---