首页 > 代码库 > BZOJ 3029 守卫者的挑战
BZOJ 3029 守卫者的挑战
一开始搞了两个dp数组,分别记到第i盘,胜j盘,拿到k个碎片和背包大小>=k的概率,然后寻思着把它们乘起来?
后来发现好像是错的。。。。这个地方不能用乘法,这两件事情是相关的。(我瞎jb猜的。。。其实是样例没过)
然后发现只要一个数组就行了。。。。收益就是+a[i],-1,问最后收益>=0,胜场>=l的方案数。。。然后直接dp。
卡内存差评。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 201 using namespace std; int n,x,l,k,a[maxn]; double p[maxn],dp[maxn][maxn][maxn<<1],ans=0; int main() { scanf("%d%d%d",&n,&l,&k); for (int i=1;i<=n;i++) {scanf("%d",&x);p[i]=x/100.0;} for (int i=1;i<=n;i++) scanf("%d",&a[i]); dp[0][0][k+200]=1.0; for (int i=0;i<n;i++) for (int j=0;j<=n;j++) for (int k=-n;k<=n;k++) { dp[i+1][j][k+200]+=dp[i][j][k+200]*(1-p[i+1]); int base=k+a[i+1]+200;base=min(base,n+200);base=max(base,-n+200); dp[i+1][j+1][base]+=dp[i][j][k+200]*p[i+1]; } for (int i=l;i<=n;i++) for (int k=0;k<=n;k++) ans+=dp[n][i][k+200]; printf("%.6lf\n",ans); return 0; }
BZOJ 3029 守卫者的挑战
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。