●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;

}

巴特西

●BZOJ 1076 [SCOI2008]奖励关

最新文章

热门文章