bzoj1076: [SCOI2008]奖励关
看数据范围直接状压DP。偶尔写了个递归的居然还WA了一次真是sad
题解 【bzoj1076: [SCOI2008]奖励关】类似背包的感觉……
对于每一种状态的每一步，对每个东西选（合法时）与不选的最大期望求和，最后/n就可以了。
代码
#include
#include
using namespace std;
int k,n,x,v[15],s[15];
double d[(1<<15)][101];
bool f[(1<<15)][101];
double cal(int now,int dep)
{
if(dep>k||f[now][dep])
return d[now][dep];
f[now][dep]=1;
double tmp=cal(now,dep+1);
for(int i=0;
i 推荐阅读
- 主席树|191101CSP模拟题解
- FWT|【LOJ #2340】【WC 2018】—州区划分（子集卷积+状压dp）
- 状压dp|[WC2018]州区划分
- c++|loj2340 WC2018 州区划分 状压dp+FWT