首页 > 代码库 > BZOJ 1076 奖励关
BZOJ 1076 奖励关
注意几点：
1.为什么要逆推？由此状态可以轻易算出彼状态是否可行，而彼状态却无法轻易还原为此状态。
2.为什么可以逆推？假设时光倒流了。。。。23333
3.注意位运算的准确，大胆写方程。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int k,n,p[150],x,limit[150];double dp[150][(1<<16)-1];int main(){ scanf("%d%d",&k,&n); for (int i=1;i<=n;i++) { scanf("%d",&p[i]); for (;;) { scanf("%d",&x); if (!x) break; limit[i]|=(1<<(x-1)); } } for (int i=k;i>=1;i--) { for (int s=0;s<=(1<<n)-1;s++) { dp[i][s]=0; for (int k=1;k<=n;k++) { if ((s&limit[k])==limit[k]) dp[i][s]+=max(dp[i+1][s],dp[i+1][s|(1<<(k-1))]+p[k]); else dp[i][s]+=dp[i+1][s]; } dp[i][s]/=n; } } printf("%.6lf\n",dp[1][0]); return 0;}
BZOJ 1076 奖励关
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。