题解 P2473 【[SCOI2008]奖励关】
LiftingTheElephant
2018-11-21 16:18:36
看到$n<=15$,你想到了什么？
# 对！
## 状态压缩！
所以我们定义$dp[i][s]$为在第i轮状态为s的最大期望得分
(s的二进制下某一位为1代表选了这个宝物)
我们又定义p[j]是第j个宝物的分数
而且,当不是逆推时,会出现不符合常理的状态。
则当不能够选这个宝物时,$dp[i][s]=dp[i][s]+dp[i+1][s]$
当能选这个宝物时,我们判断是否该选这个宝物。
若选了这个宝物(设其编号为j),则$dp[i][s]=dp[i+1][s|(1<<(j-1))]+p[j]$
(用位运算想想为什么)
所以，我们推出：
### dp[i][s]=max(dp[i+1][s],dp[i+1][s|(1<<j-1)]+p[j]);
上代码：
```
#include <iostream>
#include <cstdio>
#define re register//优化
namespace cz//自定义double类型的max函数
{
double max(double x,double y)
{
return x>y?x:y;
}
}
using namespace std;
int n,k,maxs,p[18],need[18];//need[i]是吃第i个宝物所需要吃的宝物
double dp[105][1<<15];
inline int read()//速读不说
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int main()
{
k=read(),n=read();
for(re int i=1;i<=n;i++)
{
p[i]=read();
int u;
while(scanf("%d",&u)&&u)//输入吃第i个宝物所需的宝物
need[i]|=(1<<(u-1));
}
maxs=(1<<n)-1;//最大状态是全选
for(re int i=k;i>=1;i--)//逆推
for(re int s=0;s<=maxs;s++)//循环枚举状态
{
for(re int j=1;j<=n;j++)
{
if((need[j]&s)==need[j])//若能选宝物
dp[i][s]+=cz::max(dp[i+1][s],dp[i+1][s|(1<<(j-1))]+p[j]);
else//若不能选宝物
dp[i][s]+=dp[i+1][s];
}
dp[i][s]/=n;//每个宝物被选中的概率为1/n
}
printf("%.6lf",dp[1][0]);
return 0;
}
```