[2018.10 雅礼] v 题解【概率期望】【DP】【状态压缩】

点击量：251

    这个题除了考期望、状压，考察的就是怎么压空间+时间了吧。

目录

题目背景

\(\frac 14\)遇到了一道水题，又完全不会做，于是去请教小\(\text{D}\)。小\(\text{D}\)看了\(0.607\)眼就切掉了这题，嘲讽了\(\frac 14\)一番就离开了。

于是，\(\frac 14\)只好来问你，这道题是这样的：

题目描述

有\(n\)个球排成一行，每个球的颜色为黑或白。

 

执行\(k\)次操作，第\(i(1\le i\le k)\)次操作形式如下：

• 从\([1,n-i+1]\)中，等概率随机选择一个整数\(x\)。
• 移除从左往右数的第\(x\)个球，或从右往左数的第\(x\)个球（也就是从左往右数的第\(n-i+2-x\)个）。之后，所有右侧的球的编号减\(1\)。

 

给定每个球的颜色信息，希望最大化移除的白球数量。

 

输出在最优策略下，期望的移除白球数量。误差在\(10^{-6}\)范围内，即算正确。

 

输入输出格式

输入格式：

从文件v.in中读入数据。

 

第一行，两个整数\(n,k\)。

 

第二行，一个长度为\(n\)、仅由’W’和’B’组成的字符串，第\(i\)个字符代表第\(i\)个球的颜色，’W’为白色，’B’为黑色。

 

输出格式：

输出到文件v.out中。

 

输出一行，一个浮点数，代表答案。

 

输入输出样例

输入样例#1：

3 1
BWW

输出样例#1：

1.0000000000

输入样例#2：

4 2
WBWB

输出样例#2：

1.5000000000

说明

样例1解释

如果\(x=1\)，从右侧操作，如果\(x=2\)或\(3\)，从左侧操作，均可以移除一个白球。

 

数据范围

保证\(1\le n\le 30\)，\(0\le k\le n\)。

\(\text{Subtask}\)	分值	\(n\le\)	其他限制
\(1\)	\(20\)	\(5\)	无
\(2\)	\(25\)	\(20\)	无
\(3\)	\(1\)	\(30\)	保证\(k=0\)或\(k=n\)
\(4\)	\(1\)		保证字符串所有字符相同
\(5\)	\(19\)		保证字符串只有一个’W’
\(6\)	\(19\)		保证字符串只有一个’B’
\(7\)	\(15\)		无

题解：

    我现在算是服了“期望题大都得倒着做”这一性质定律，尤其是期望DP，这样做决策的时候取\(max\)会方便许多。

    因为这个题要求期望最大，因此引入期望DP，这个题用了spj没用逆元好评，我们对每个状态中的每个对称位置做决策，选出删掉哪个球所能得到的期望最大。看出这个题的DP思路后就可以开始DP了，而这个题\(n\le 30\)，考虑尝试状压。

    但是实际上\(2^{30}\)所能表示的状态也超过了一亿，我们发现，这个题的初始串是固定的，因此所能引申出来的状态一定非常少，一定跑不到上界，出题人表示这个实际上界会达到\(\sum_{i=1}^{n+1}Fib(i)=2,178,308\)，因此时间是不用担心的，

    然后我们定义dp数组\(f_{(i,sta)}\)表示还剩下\(i\)个小球，颜色状态是\(sta\)时，期望去掉白球个数。每次枚举每个对称位置，这个位置被随机选到的概率是\(frac 2n\)，中间位置要特判\(\frac 1n\)。按长度从大到小做，对于一个状态，决策删掉两个球中的哪个更优，这里可以预处理，也可以写一个del函数。然后从删掉后的状态转移来就可以了，如果删掉的这个球是白球，转移的时候要在式子后面加上\(1\)。

    最终答案就是\(f_{n,初始状态}\)   。

    但是我们发现开\(30\times 2^{30}\)的数组非常不现实。但是当\(n\)很大的时候状态又比较小，因此可以用std::map存，虽说map用了RBT，但是数据小了没有什么影响，那么我们就决定把大于\(20\)的状态扔到map里，小于20的开double数组。

    但是发现大于20的状态还是比较多的，导致了TLE，但是开更大的double数组会MLE，为了开更大的double数组，我们可以把第一维的系数\(n\)换成常数\(2\)，让二进制状态的最高位所在的位置来确定这个二进制串的长度。这样一来，用数组存的状态可以达到长度24。此时时间复杂度和空间复杂度就都能达到了。

Code：

#include<map>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#define eps 1e-8
using std::map;
using std::max;
map<int,double>m[31];
double f[33554440];
char s[50];
int n,k;
int del(int x,int t)//删掉x的第t位（最右边是第一位）
{
    int r=x&(2147483647-(1<<t)+1);
    r>>=1;
    r|=x&((1<<(t-1))-1);
    return r;
}
int judge(int x,int t)
{
    return (x>>(t-1))&1;
}
bool used[33554440];
double dfs(int num,int x)
{

    if(num==n-k)
        return 0;
    if(num>24)
    {
        if(m[num].find(x)!=m[num].end())
            return m[num][x];
        double &sum=m[num][x];
        for(int i=1;i<=num>>1;++i)//judge是判断那一位是不是1
            sum+=2.0*max(dfs(num-1,del(x,i))+judge(x,i),dfs(num-1,del(x,num-i+1))+judge(x,num-i+1));
        if(num&1)
            sum+=1.0*(dfs(num-1,del(x,num/2+1))+judge(x,num/2+1));
        return sum/=num;
    }
    else
    {
        int cur=x|(1<<num);
        if(used[cur])
            return f[cur];
        double &sum=f[cur];
        used[cur]=1;
        for(int i=1;i<=num>>1;++i)
            sum+=2.0*max(dfs(num-1,del(x,i))+judge(x,i),dfs(num-1,del(x,num-i+1))+judge(x,num-i+1));
        if(num&1)
            sum+=1.0*(dfs(num-1,del(x,num/2+1))+judge(x,num/2+1));
        return sum/=num;
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    if(!k)
    {
        puts("0");
        return 0;
    }
    scanf("%s",s+1);
    int ori=0;
    for(int i=1;i<=n;++i)
    {
        ori<<=1;
        ori+=(s[i]=='W');
    }
    printf("%.8lf\n",dfs(n,ori));
    return 0;
}