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

}