首页 > 其他分享 >at_dp_j-ti-jie

at_dp_j-ti-jie

时间:2024-05-08 18:24:12浏览次数:19  
标签:jie frac 寿司 times 枚举 ti 盘子 dp

AT_dp_j

思路

期望 dp。

设 $dp_{i,j,k,l}$ 表示当前有 $0,1,2,3$ 个寿司的盘子数有 $i,j,k,l$ 个时的期望次数。

显然 MLE。但可以发现 $i+j+k+l=n$,所以可以去掉一维。

设 $dp_{i,j,k}$ 表示当前有 $1,2,3$ 个寿司的盘子数有 $i,j,k$ 个时的期望次数。

首先有 $dp_{0,0,0}=0$。

对于一个状态 $dp_{i,j,k}$ 可以有四个状态得到。可以选装了 $1,2,3$ 个寿司的盘子,或者选空盘子,即浪费一步。

所以有:

$dp_{i,j,k}=\frac {i}{n}\times dp_{i-1,j,k}+\frac {j}{n}\times dp_{i+1,j-1,k}+\frac {k}{n}\times dp_{i,j+1,k-1}+\frac {n-i-j-k}{n}\times (dp_{i,j,k}+1)$

左右两边都有 $dp_{i,j,k}$,进行移项。得到:

$\frac {i+j+k}{n}\times dp_{i,j,k}=\frac {i}{n}\times dp_{i-1,j,k}+\frac {j}{n}\times dp_{i+1,j-1,k}+\frac {k}{n}\times dp_{i,j+1,k-1}+\frac {n-i-j-k}{n}$

$dp_{i,j,k}=(\frac {i}{n}\times dp_{i-1,j,k}+\frac {j}{n}\times dp_{i+1,j-1,k}+\frac {k}{n}\times dp_{i,j+1,k-1}+\frac {n-i-j-k}{n}) \times \frac {n}{i+j+k}$

$dp_{i,j,k}=\frac {i}{i+j+k}\times dp_{i-1,j,k}+\frac {j}{i+j+k}\times dp_{i+1,j-1,k}+\frac {k}{i+j+k}\times dp_{i,j+1,k-1}+\frac {n-i-j-k}{i+j+k}$

但是 $dp_{i,j,k}$ 需要由 $dp_{i-1,j,k},dp_{i+1,j-1,k},dp_{i,j+1,k-1}$ 计算,不符合正常理解里的 dp。所以设 $dp_{k,j,i}$ 表示当前有 $3,2,1$ 个寿司的盘子数有 $k,j,i$ 个时的期望次数。改变枚举次序,先枚举 $k$,再枚举 $j$,最后再枚举 $i$。

代码不长。

code

signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),cnt[a[i]]++;
	dp[0][0][0]=0;
//	cout<<cnt[1]<<" "<<cnt[2]<<" "<<cnt[3]<<"\n";
	for(int k=0;k<=n;k++){
		for(int j=0;j<=n;j++){
			for(int i=0;i<=n;i++){
				if(i||j||k){
					dp[k][j][i]=1.0*(n-i-j-k)/(i+j+k);
					if(i)dp[k][j][i]+=1.0*i/(i+j+k)*(dp[k][j][i-1]+1);
					if(j)dp[k][j][i]+=1.0*j/(i+j+k)*(dp[k][j-1][i+1]+1);
					if(k)dp[k][j][i]+=1.0*k/(i+j+k)*(dp[k-1][j+1][i]+1);
//					cout<<i<<" "<<j<<" "<<k<<" ";
//					printf("%10lf\n",dp[k][j][i]);
				}
			}
		}
	}
	printf("%.10lf",dp[cnt[3]][cnt[2]][cnt[1]]);
}

标签:jie,frac,寿司,times,枚举,ti,盘子,dp
From: https://www.cnblogs.com/yhddd/p/18180561

相关文章

  • a-story-of-the-small-p-ti-jie
    「2020-2021集训队作业」AstoryofTheSmallP题意给定$N,m,k$,求有多少个正整数序列h满足:h的长度$n$满足$1\leqn\leqN$。$1\leqh_i\leqm$。正好存在$k$个$i$满足$h_i<h_{i+1}$。答案模$998244353$。$2\leqN,m,k\leq2^{19},(N-k+1)\timesm\l......
  • arc162f-ti-jie
    arc162f思路$a_{x1,y2}\timesa_{x2,y2}\leqa_{x1,y2}\timesa_{x2,y1}$改为所有$a_{x1,y1}=a_{x2,y2}=1$,都有$a_{x1,y2}=a_{x2,y1}=1$。观察发现,第$i$行$a_{i,j_1}=\ldots=a_{i,j_{num}}=1,(j_1<\ldots<j_{num})$,第$ii,(ii>i)$行能取$1$的位置是$[1,j_1-1]$和......
  • arc119f-ti-jie
    arc119f自动机写法。开始在做的时候题解没讲每个节点代表什么状态,自己推了一遍,记录一下。思路计数,求有多少种替换方式使得$0$到$n$存在一条长度小于等于$K$的路径。可以做$O(n^3)$的dp。设$dp_{i,a,b}$表示前$i$个位置,最近的$A$和$B$分别在$a$和$b$。官方......
  • arc106d-ti-jie
    ARC106D思路左边到右边不好,改为任意一个到另一个。$$ans_x=\frac{1}{2}(\sum_in\sum_jn(a_i+a_j)x-\sum_in(2\timesa_i)^x)$$拆开$k$次方。$$(a_i+a_j)x=\sum_{k=0}x(\binom{x}{k}\times{a_i}^k\times{a_j}^{x-k})$$$$ans_x=\frac{1}{2}(\sum_{k=0}x(\sum_in{a_i}^......
  • agc049a-ti-jie
    agc049a思路期望。与CF280C相似的思路。每个点最多被做一次,或者被其他点影响。设$f_i$表示$i$是否被选,为$0$或$1$。答案为$E[\sumf_i]$,即$\sumf_i$的期望。$$ans=E[\sumf_i]=\sumE[f_i]=\sump_i$$所以答案为每个点被选的概率的和。能影响点$i$使其不被......
  • abc349g-ti-jie
    abc349g思路从前往后枚举$i$,每次对$i+1\lej\lei+a_i$的$j$赋值$b_j=b_{i\times2-j}$。同时有$b_{i+a_i+1}\neb_{i-a_i-1}$。用$ban_{i,j}$记录$i$不能是$j$,如果要给$i$赋值就选最小的。最直接的就是并查集倍增将两段区间并起来。可以用类似马拉车的思路得......
  • Elements in iteration expect to have 'v-bind:key' directives.
    当组件中使用v-for时,如果不指定key,则会有红色警告信息。解决方案如下。方案一:绑定key(亲试有效)//方式一<liv-for="(item,index)inlist":key="index">//方式二<liv-for="(item,index)inlist":key="item.id">//方式三<liv-for="(item,in......
  • GeometryCollection 的类型映射器(TypeHandler)
    byemanjusakafromhttps://www.emanjusaka.top/2024/05/mybatis-typeHandler-geometryCollection彼岸花开可奈何本文欢迎分享与聚合,全文转载请留下原文地址。GeometryCollection是GeoJSON数据模型中的一个类型,用于表示一个几何对象的集合。MySQL8中支持了GeometryCol......
  • 为什么在有@Transactional注解的方法,一定要加rollbackFor异常回滚的异常类型?
    在spring项目中,@Transactional注解默认会回滚运行时异常(RuntimeException)及其子类当你在一个有@Transactional注解方法里面抛了一个Expection类型的异常,呢它是不支持事务回滚的,异常继承体系我们在一个方法里面要对事务进行操作,如果要抛异常,应该抛出untimeException,不能直接......
  • spring刷题记录——to be continue
    在牛客网刷的题目,类似于补基础了?这里按照知识点进行分类,因为发现有些同样的知识点不同的题目还是很痛苦。这里就不用颜色标记了,因为我觉得都要记。Spring容器篇Spring容器也叫做Ioc容器(Ioc,在我之前写的随笔里面也有谈到),本质上就是一个工厂。Sp......