●BZOJ 1076 [SCOI2008]奖励关

题链:

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

期望dp。
(模糊的题意,2333)
题中的:"现在决定不吃的宝物以后也不能再吃"应该是指:当前可以吃时,即面临选择时,如果选择了不吃,那么以后就都不能吃该宝物了。
(如果不这么理解的话,感觉dp转移解释不通)

dp[i][S]表示到了第i次机会,已经吃了的糖果的集合为S时,以后(包括这次)所期望的最高得分。
依次枚举这次的随机出来的宝物j:
如果满足前提条件:
dp[i][S]+=max(dp[i+1][S],dp[i+1][S|idx(j)]+val[j])/N
如果不满足前提条件,那么就只有一种转移了:
dp[i][S]+=dp[i+1][S]/N

为什么这样转移就可以满足题中的那个鬼畜的"以后就不能吃的"限制了呢。
先看第一个转移:如果当前选择了不吃更优的话,那么以后当然也不会吃的。
如果当前选择了吃更优,那么以后也一定会吃。
(换句话说,不会存在这样一种dp转移:在后来吃了这个宝物,但是现在可以吃的时候却选择不吃了)
然后第二个转移:因为手动"更改"了一下题意,这么转移就当然没问题啦。

代码:

#include<bits/stdc++.h>
using namespace std;
double dp[105][1<<15];
int pre[20],val[20];
int N,K;
int idx(int i){
return 1<<(i-1);
}
int main(){
ios::sync_with_stdio(0);
cin>>K>>N;
for(int i=1,x;i<=N;i++){
cin>>val[i];
while(cin>>x&&x) pre[i]|=idx(x);
}
for(int i=K;i>=1;i--)
for(int S=0;S<(1<<N);S++)
for(int j=1;j<=N;j++){
double k=1.0/N; /*注释的是枚举的S表示来源dp[i+1][S]的S,注意if的嵌套。
(为了满足题意:当前宝物可吃但是选择不吃那么以后就不能吃了,所以只有不满足前提条件是才能执行else语句)
if((S&pre[j])==pre[j]){
if(!(S&idx(j))) continue;
dp[i][S]+=max(k*(dp[i+1][S]+val[j]),k*dp[i+1][S]);
dp[i][S^idx(j)]+=max(k*(dp[i+1][S]+val[j]),k*dp[i+1][S^idx(j)]);
}
else dp[i][S]+=k*dp[i+1][S];*/ //以下是枚举的S表示当前dp[i][S]的那个S
if((S&pre[j])==pre[j])
dp[i][S]+=max(k*dp[i+1][S],k*(dp[i+1][S|idx(j)]+val[j]));
else dp[i][S]+=k*dp[i+1][S];
}
cout<<fixed<<setprecision(6)<<dp[1][0]<<endl;
return 0;
}

  

上一篇:leecode第一百六十题(相交链表)


下一篇:Mac上的软件使用介绍