本文最后更新于:2020年4月11日 下午

问题简述

有一列连续坐着1到K的火车。
这里有N个人按顺序来。
每个人都有以下两种感觉之一。

  • 无论如何都要坐下:坐在最低的座位上。

  • 如果愿意的话,想坐下来:坐在编号最小的座位上,两边都没有人。

  • 无论如何,如果没有符合条件的座位,则必须坐下。
    给出了每个人感觉到前者的概率$p [i]$。

  • 最后空缺的预期人数是多少?

问题分析

如果您负担得起,想要坐的人将比坐在前面的人领先一步。

因此,仅需要将[在中间空出的座位数]和[最后连续空出的座位数]作为状态,并且DP将到达该状态的可能性作为状态。

前者的情绪首先坐满了被跳过的座位,而后者的情绪坐着在连续的空缺座位中创建一个被跳过的座位。

棘手的部分是两端的处理,这是唯一需要处理的异常。

这道题可以用动态规划了。

核心部分伪$Code$

int N,K;
double dp[2][300][300];
double p;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	if(K==1) dp[0][0][K]=1;
	else dp[0][K][0]=1;
	
	FOR(i,N) {
		int cur=i%2,tar=cur^1;
		cin>>x;
		p=x*0.01;
		ZERO(dp[tar]);
		
		FOR(x,K+1) FOR(y,K+1) {
			
			//ts
			if(y>0) dp[tar][x][y-1] += p*dp[cur][x][y];
			else if(x==2) dp[tar][0][y+1] += p*dp[cur][x][y];
			else if(x>2) dp[tar][x-1][y] += p*dp[cur][x][y];
			else dp[tar][x][y] += p*dp[cur][x][y];
			
			//ys
			if(K==1 && y==1) dp[tar][0][0] += (1-p)*dp[cur][x][y];
			else if(x==K) {
				if(K==1) dp[tar][0][0] += (1-p)*dp[cur][x][y];
				if(K==2) dp[tar][0][1] += (1-p)*dp[cur][x][y];
				else dp[tar][K-1][0] += (1-p)*dp[cur][x][y];
			}
			else if(x==2) dp[tar][0][y+1] += (1-p)*dp[cur][x][y];
			else if(x==3) dp[tar][0][y+2] += (1-p)*dp[cur][x][y];
			else if(x>3) dp[tar][x-2][y+1] += (1-p)*dp[cur][x][y];
			else dp[tar][x][y] += (1-p)*dp[cur][x][y];
		}
	}
	
	double ret=0;
	FOR(x,K+1) FOR(y,K+1) ret += dp[N%2][x][y]*(x+y);
	_P("%.12lf\n",ret);
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT966 【JOI 国の買い物事情 (Shopping in JOI Kingdom)】 上一篇
题解 AT944 【注文の多い高橋商店】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。