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

作者: wjyyy 分类: DP,概率期望,状态压缩,解题报告 发布时间: 2018-10-16 08:52

点击量:14

 

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

 

题目背景

\(\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;
}

说点什么

avatar
  Subscribe  
提醒
/* */