[HackerRank]Choosing White Balls
题目大意：
有\(n(n\le30)\)个球排成一行，每个球的颜色为黑或白。
执行\(k\)次操作，第\(i\)次操作形式如下：
- 从\([1,n−i+1]\)中，等概率随机选择一个整数\(x\)。
- 移除从左往右数的第\(x\)个球，或从右往左数的第\(x\)个球。之后，所有右侧的球的编号减\(1\)。
给定每个球的颜色信息，求在最优策略下，期望的移除白球数量最大值。
思路：
状压DP+哈希表。
源代码：
#include<cstdio>
#include<cctype>
#include<ext/pb_ds/assoc_container.hpp>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
inline int getval() {
register char ch;
while(!isalpha(ch=getchar()));
return ch=='W';
}
typedef long long int64;
int n,m;
__gnu_pbds::cc_hash_table<int64,double> map;
inline int del(const int &s,const int &i) {
return (s>>(i+1)<<i)+(s&((1<<i)-1));
}
inline int bit(const int &s,const int &i) {
return (s>>i)&1;
}
double dfs(const int &s,const int &cnt) {
if(cnt<=n-m) return 0;
const int64 p=(1ll<<cnt)|s;
if(map.find(p)!=map.end()) return map[p];
double ret=0;
for(register int i=0;i<cnt;i++) {
double tmp=0;
const int j=cnt-i-1;
tmp=std::max(tmp,dfs(del(s,i),cnt-1)+bit(s,i));
tmp=std::max(tmp,dfs(del(s,j),cnt-1)+bit(s,j));
ret+=tmp;
}
ret/=cnt;
return map[p]=ret;
}
int main() {
n=getint(),m=getint();
int all=0;
for(register int i=0;i<n;i++) {
all=all<<1|getval();
}
printf("%.8f\n",dfs(all,n));
return 0;
}