bzoj千题计划206:bzoj1076: [SCOI2008]奖励关

时间:2023-02-07 03:42:06

http://www.lydsy.com/JudgeOnline/problem.php?id=1076

很容易想到方程

dp[i][j]表示抛出了i个宝物,已选宝物状态为j的期望最大得分

初始化dp[0][0]=0,其余都为负无穷

设宝物i的前提宝物集合为pre[i]

枚举第i次抛,当前已选宝物状态j,这一次抛出了第l个宝物

若 j&pre[l]==pre[l]  那么这个宝物就可以选,也可以不选

选,转移到dp[i+1][j|1<<l-1]

不选,转移到dp[i+1][j]

否则,这个宝物一定不能选,转移到dp[i+1][j]

那么问题来了,最后宝物状态集合是什么,最后输出什么?

Σ dp[n][s]/s ?

错误

因为 最后每种宝物状态出现的概率不一样

那就再递推个每种状态出现的概率?

尝试写了一发,

但状态出现的概率到后面会非常小非常小,小到让我存不了。。。

所以本思路GG

对了两个点,+递推出现概率的代码:

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; int val[],pre[]; int bit[]; double dp[][<<];
double f[][<<];
bool vis[][<<]; const double eps=1e-; void read(int &x)
{
x=; int f=; char c=getchar();
while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
x*=f;
} bool dcmp(double a,double b)
{
return fabs(a-b)<eps;
} int main()
{
int k,n;
read(k); read(n);
bit[]=;
for(int i=;i<=n;++i) bit[i]=bit[i-]<<;
int x;
for(int i=;i<=n;++i)
{
read(val[i]);
while()
{
read(x);
if(!x) break;
pre[i]+=bit[x-];
}
}
int s=bit[n];
vis[][]=true;
f[][]=;
for(int i=;i<k;++i)
for(int j=;j<s;++j)
if(vis[i][j])
{
for(int l=;l<=n;++l)
if((j&pre[l])==pre[l])
{
if((dp[i][j]+val[l])*f[i][j]/n>dp[i+][j|bit[l-]]*f[i+][j|bit[l-]])
{
dp[i+][j|bit[l-]]=dp[i][j]+val[l];
f[i+][j|bit[l-]]=f[i][j]/n;
vis[i+][j|bit[l-]]=true;
}
else if(dcmp((dp[i][j]+val[l])*f[i][j]/n,dp[i+][j|bit[l-]]*f[i+][j|bit[l-]]))
{
f[i+][j|bit[l-]]+=f[i][j]/n;
vis[i+][j|bit[l-]]=true;
}
}
}
double ans=;
for(int i=;i<s;++i) ans+=dp[k][i]*f[k][i];
printf("%.6lf",ans);
}

正解:倒推

dp[i][j] 表示抛了i个宝物,所选状态为j的最大期望得分

枚举这次抛出第l种宝物

能选,j&pre[l]==pre[l]

那么从选与不选里取最优解,dp[i][j]+=max(dp[i+1][j],dp[i+1][j|1<<l-1])

不能选 dp[i][j]+=dp[i+1][j]

对于dp[i][j] 来说,枚举n种可能抛出哪种宝物,概率是同样的

所以最后dp[i][j]/n 即是状态的期望得分

最后输出dp[n][0]

#include<cstdio>
#include<iostream> using namespace std; int val[],pre[]; int bit[]; double dp[][<<]; void read(int &x)
{
x=; int f=; char c=getchar();
while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
x*=f;
} int main()
{
int k,n;
read(k); read(n);
bit[]=;
for(int i=;i<=n;++i) bit[i]=bit[i-]<<;
int x;
for(int i=;i<=n;++i)
{
read(val[i]);
while()
{
read(x);
if(!x) break;
pre[i]+=bit[x-];
}
}
int S=bit[n];
for(int i=k;i;--i)
for(int j=;j<S;++j)
{
for(int l=;l<=n;++l)
if((j&pre[l])==pre[l]) dp[i][j]+=max(dp[i+][j],dp[i+][j|bit[l-]]+val[l]);
else dp[i][j]+=dp[i+][j];
dp[i][j]/=n;
}
printf("%.6lf",dp[][]);
}

bzoj千题计划206:bzoj1076: [SCOI2008]奖励关的更多相关文章

  1. BZOJ1076 &lbrack;SCOI2008&rsqb;奖励关 【状压dp &plus; 数学期望】

    1076: [SCOI2008]奖励关 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 3074  Solved: 1599 [Submit][Sta ...

  2. &lbrack;BZOJ1076&rsqb;&lbrack;SCOI2008&rsqb;奖励关 状压dp

    1076: [SCOI2008]奖励关 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 3070  Solved: 1595[Submit][Statu ...

  3. bzoj1076&colon; &lbrack;SCOI2008&rsqb;奖励关&lpar;期望dp&plus;状压dp&rpar;

    1076: [SCOI2008]奖励关 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 2989  Solved: 1557[Submit][Statu ...

  4. bzoj千题计划300:bzoj4823&colon; &lbrack;Cqoi2017&rsqb;老C的方块

    http://www.lydsy.com/JudgeOnline/problem.php?id=4823 讨厌的形状就是四联通图 且左右各连一个方块 那么破坏所有满足条件的四联通就好了 按上图方式染色 ...

  5. BZOJ1076&colon;&lbrack;SCOI2008&rsqb;奖励关&lpar;状压DP&comma;期望&rpar;

    Description 你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关.在这个奖励关里,系统将依次随机抛出k次宝物, 每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的 ...

  6. &lbrack;BZOJ1076&rsqb;&lbrack;SCOI2008&rsqb;奖励关解题报告&vert;状压DP

    你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关.在这个奖励关里,系统将依次随机抛出k次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃). 宝 ...

  7. Bzoj1076 &lbrack;SCOI2008&rsqb;奖励关

    Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1935  Solved: 1053 Description 你正在玩你最喜欢的电子游戏,并且刚刚进入一 ...

  8. BZOJ1076&colon; &lbrack;SCOI2008&rsqb;奖励关【状压DP&plus;期望DP】

    Description 你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关.在这个奖励关里,系统将依次随机抛出k次宝物, 每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的 ...

  9. bzoj千题计划179:bzoj1237&colon; &lbrack;SCOI2008&rsqb;配对

    http://www.lydsy.com/JudgeOnline/problem.php?id=1237 如果没有相同的数不能配对的限制 那就是排好序后 Σ abs(ai-bi) 相同的数不能配对 交 ...

随机推荐

  1. 导出excel表功能

    前台: <asp:Button ID="btndao" runat="server"  Text="导出excel文件" onclic ...

  2. LINUX单网卡绑定多个IP

    在linux下,我们有时候需要给单网卡设置不同的IP地址,这样就涉及到单网卡绑定多个IP地址的情况.使用本方法可以方便的为单网卡绑定多个IP地址.笔者使用的环境是centos5.6,应该在fedora ...

  3. javascript&lpar;3&rpar;

    使用javascript改进链接 摘自<javascript基础教程> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Trans ...

  4. MacTex XeLaTex xdvipdfmx&colon;fatal&colon; pdf&lowbar;ref&lowbar;obj&lpar;&rpar;&colon; passed invalid object&period; 报错的解决方法

    在使用MacTex配合TexStudio编译beamer的时候,爆出如下错误, xdvipdfmx:fatal: pdf_ref_obj(): passed invalid object. 结果尝试其 ...

  5. 使用 qemu 搭建内核开发环境

    本文主要介绍在 MacOS 上使用 qemu 搭建 Linux Kernel 的开发环境.(在开始之前需要注意的是,本文中的 Linux 开发环境是一个远程服务器,而 qemu 被安装在本地的 Mac ...

  6. CentOS Ubantu linux中实用系统相关常用命令

    系统信息相关命令 本节内容主要是为了方便通过远程终端维护服务器时,查看服务器上当前 系统日期和时间 / 磁盘空间占用情况 / 程序执行情况 本小结学习的终端命令基本都是查询命令,通过这些命令对系统资源 ...

  7. 值得推荐的五大敏捷PHP开发框架

    各位开发者,对于在HTML中混乱使用PHP的人来说,我们给大家推荐几款PHP敏捷开发的框架,以及它们为什么能够流行. 在我们开始之前,先了解敏捷开发是个什么东东. 敏捷是一种软件开发方法,每次开发计划 ...

  8. 从零開始学android&amp&semi;lt&semi;使用嵌套布局实现计算器界面&period;十七&period;&amp&semi;gt&semi;

    所谓的嵌套布局就是在一个文件里嵌套多个布局文件 <span style="font-size:18px;"> <LinearLayout android:layo ...

  9. 【BZOJ4919】&lbrack;Lydsy六月月赛&rsqb;大根堆 线段树合并

    [BZOJ4919][Lydsy六月月赛]大根堆 Description 给定一棵n个节点的有根树,编号依次为1到n,其中1号点为根节点.每个点有一个权值v_i. 你需要将这棵树转化成一个大根堆.确切 ...

  10. mvc学习-编辑提交需要注意-mvc重点

    示例代码: // GET: /Movies/Edit/5 public ActionResult Edit(int? id) { if (id == null) { return new HttpSt ...