注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1076][SCOI2008]奖励关  

2014-11-01 17:10:34|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1076: [SCOI2008]奖励关

给概率题跪烂了……
想了快一天QAQ然后还是不会
看了题解又想了半下午
终于知道自己的做法为啥是错误的了。。
感谢GTY神犇的讲解
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
const int N = 15+2;
const int M = 100;
int n,m,two[50],need[20],fen[20];
int scan(){int i=0;scanf("%d",&i);return i;}
struct state{int i,d;state(int ii,int aa):i(ii),d(aa){}};
double f[M][1<<15];
int v[M][1<<15];
queue<state>dui;
double once;
void update(state next,double F){
int &vn = v[next.i][next.d];
double &fn = f[next.i][next.d];
if(!vn){vn = 1;dui.push(next);}
fn += F;
}
int main(){
int i,j,k,a,b,c;
m = scan();n = scan();
once = 1./n;
for(i=1,two[0] = 1;i<=30;i++)two[i] = two[i-1]*2;
for(i=1;i<=n;i++){
fen[i] = scan();
while((b = scan())) need[i] += two[b-1];
}
for(i=m;i;i--)
for(j=0;j<two[n];j++){
for(k=1;k<=n;k++)
if((j&need[k]) == need[k]){
f[i][j] += max(f[i+1][j],f[i+1][j|two[k-1]] + fen[k]);
}else{
f[i][j] += f[i+1][j];
}
f[i][j] *= once;
}
printf("%.6f",f[1][0]);
return 0;
}

题解:
DP
f[i][j]表示当前是第i个,已经选了物品种类的集合是j
需要倒着做
枚举每个物品k
如果j包括了k的所有前提物品
f[i][j] += max( f[i+1][j], f[i+1][j | (1<<(k-1))]+val[k] )/n
否则
f[i][j] +=  f[i+1][j]/n
------------------------------------------------------------------------------------------------------------------------------------------------
一些问题:
一开始我的想法是正着做,对于物品价值的正负分成两种情况。
但是这个方法的问题在于最后会有无数的状态,你不知道哪些是优的状态哪些是不优的,而倒着做因为最后只有一个合法状态所以不需要考虑。
  评论这张
 
阅读(53)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017