雅礼集训 Day3 T2 v 解题报告

时间:2022-03-25 23:01:26
雅礼集训 Day3 T2 v 解题报告

v

题目背景

\(\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\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\) \(30\) 保证字符串所有字符相同
\(5\) \(19\) \(30\) 保证字符串只有一个'W'
\(6\) \(19\) \(30\) 保证字符串只有一个'B'
\(7\) \(15\) \(30\)

挂了一堆部分分。。。惨无人道啊。

45pts状压一下

\(dp_{i,sta}=\sum max(dp_{i-1,to1},dp_{i-1,to2})\)

因为要倒着做所以直接记搜就行了

剩下的部分分瞎搞一下

100pts就是把状态存储小的用数组存,大的用map...

我太菜而最后一个点实在是卡不过去了


Code:

#include <cstdio>
#include <cstring>
#include <map>
int n,k;
std::map <int,double> dp[31];
double dp0[24][1<<23];
char s[32];
double max(double x,double y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
double dfs(int sta,int siz)
{
if(siz==n-k) return 0;
if(siz>23&&dp[siz].find(sta)!=dp[siz].end()) return dp[siz][sta];
if(siz<=23&&dp0[siz][sta]!=-1.0) return dp0[siz][sta];
double sum=0;
for(int i=1;i<=siz>>1;i++)
{
int co1=sta>>i-1&1,co2=sta>>siz-i&1;
int to1=sta>>1&~((1<<i-1)-1)|sta&(1<<i-1)-1;
int to2=sta>>1&~((1<<siz-i)-1)|sta&((1<<siz-i)-1);
sum+=2*max(dfs(to1,siz-1)+co1,dfs(to2,siz-1)+co2);
}
if(siz&1)
{
int i=siz+1>>1;
int to=sta>>1&~((1<<i-1)-1)|sta&(1<<i-1)-1;
int co=sta>>i-1&1;
sum+=dfs(to,siz-1)+co;
}
sum=sum/siz;
return siz>23?dp[siz][sta]=sum:dp0[siz][sta]=sum;
}
int main()
{
scanf("%d%d%s",&n,&k,s);
int st=0;
for(int i=n-k+1;i<=min(23,n);i++)
for(int j=0;j<1<<i;j++)
dp0[i][j]=-1.0;
for(int i=1;i<=n;i++)
st|=(s[i-1]=='W')<<n-i;
printf("%.8lf\n",dfs(st,n));
return 0;
}

2018.10.3

UPT on 2018.10.12:我卡过去了,并且学会了一个小技巧

发现状态数组实际上有很多浪费,因为每个\(i\)的状态都是\(2^i\)的,我们没必要开两维

直接开一维\(dp_{sta}\)就可以。

但是这样可能造成重复之类的,我们可以给某一个长度为\(i\)的维度把\(i+1\)位打1标记,代表这是第\(i\)维的

这是很常见的一个技巧了

Code:

// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <map>
int n,k;
std::map <int,double> dp;
double dp0[1<<25];
char s[32];
double max(double x,double y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
double dfs(int sta,int siz)
{
if(siz==n-k) return 0;
if(siz>24&&dp.find(sta)!=dp.end()) return dp[sta];
if(siz<=24&&dp0[sta]!=-1.0) return dp0[sta];
double sum=0;
for(int i=1;i<=siz>>1;i++)
{
int co1=sta>>i-1&1,co2=sta>>siz-i&1;
int to1=sta>>1&~((1<<i-1)-1)|sta&(1<<i-1)-1;
int to2=sta>>1&~((1<<siz-i)-1)|sta&((1<<siz-i)-1);
sum+=2.0*max(dfs(to1,siz-1)+co1,dfs(to2,siz-1)+co2)/siz;
}
if(siz&1)
{
int i=siz+1>>1;
int to=sta>>1&~((1<<i-1)-1)|sta&(1<<i-1)-1;
int co=sta>>i-1&1;
sum+=(dfs(to,siz-1)+co)/siz;
}
return siz>24?dp[sta]=sum:dp0[sta]=sum;
}
int main()
{
scanf("%d%d%s",&n,&k,s);
int st=0;
for(int i=0;i<1<<25;i++)
dp0[i]=-1.0;
for(int i=1;i<=n;i++)
st|=(s[i-1]=='W')<<n-i;
st|=1<<n;
printf("%.8lf\n",dfs(st,n));
return 0;
}