【JZOJ1468】V

题目

思路

长度为 \(n\) 的 01 串的字串数量上界是 \(O(\sum^{n}_{i=1})fib[i]\)，其中 \(fib\) 是斐波那契数列。
所以 \(n\leq 30\) 证明本质不同的字串数量是可以接受枚举的复杂度的。所以在 \(O(2^n\times n)\) 的基础上，将 dp 改为记忆化搜索即可。
注意到用状压时状态很大，所以直接用 \(\operatorname{STL::map}\) 即可。
时间复杂度 \(O(\) 玄学 \()\)。
事实上，我最终没有卡过最后一个点。人傻常数大，我很抱歉。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;

const int N=35,MAXN=(1<<30);
int n,m;
char ch[N];
map<int,double> f;

__attribute__((optimize("O3"))) inline int get(int x,int len)
{	
	int s=(1<<len+1),cnt=1;
	for (int i=0;i<n;i++)
		if (x&(1<<i))
		{
			if (ch[i]=='W') s|=(1<<cnt);
			cnt++;
		}
	return s;
}

__attribute__((optimize("O3"))) inline int count(int x)
{
	int cnt=0;
	for (int i=0;i<n;i++)
		if (x&(1<<i)) cnt+=(ch[i]=='W');
	return cnt;
}

__attribute__((optimize("O3"))) inline int find(int S,int k)
{
	for (int i=0;i<n;i++)
	{
		if (S&(1<<i)) k--;
		if (!k) return i;
	}
}

__attribute__((optimize("O3"))) inline int dfs(int S,int len)
{
	int s=get(S,len);
	if (len==n-m) f[s]=1.0*count(S);
	if (f.count(s)) return s;
	for (register int i=1;i<=len;i++)
		f[s]+=min(f[dfs(S^(1<<find(S,i)),len-1)],f[dfs(S^(1<<find(S,len-i+1)),len-1)]);
	f[s]=f[s]/len;
	return s;
}

int main()
{
	scanf("%d%d",&n,&m);
	if (!m) return printf("0.000000"),0;
	scanf("%s",ch);
	int Maxn=(1<<n)-1;
	dfs(Maxn,n);
	printf("%.6lf",1.0*count(Maxn)-1.0*f[get(Maxn,n)]);
	return 0;
}