题目链接：vjudge

大意：有两个人参加一场游戏，这个游戏在一个编号为\(0\text~n-1\)的轮盘上进行，一开始轮盘上的数字均为0；一共有\(m\)轮，每一轮都有一个操作参数\(s_i\)，主持人等概率置顶某个位置\(j\)，从\(j\)开始数\(s_i\)个位置，每个位置上的数+1（这两个人均不知道主持人所选定的位置）。\(m\)轮结束之后，Alice指定一个位置，主持人告知该位上的数。Bob根据Alice得到的回答再选定一个位置（可以重复），获得该位置上的数。他们的游戏得分就是所获得的两数之和。求其期望（好长啊qwq）

分析

被800搞自闭了

我们将格子编号+1，方便叙述

记\(dp[i][j][k]\)为在进行到第\(i\)轮的时候，第1位上的数字为\(j\)时，第\(k\)位上数字的期望

因为我们总可以将Alice所选的位置看作是第1位，因此答案就是

我们再记一个辅助数组\(f[i][j]\)，表示在第\(i\)轮的时候，第1为上的数是\(j\)的概率

这个玩意比较好转移：

特判一下\(j=0\)时只有一种转移

那么我们接着处理\(dp​\)数组的转移，容易知道\(dp[i][j][k]​\)也会是由\(dp[i-1][j-1][k]​\)和\(dp[i-1][j][k]​\)转移而来

具体的实现的话我们需要第二个辅助数组\(tim[i][j]\)表示当所选取的+1区间长度为\(i\)，且保证区间包含第1位时，包含第\(j\)位的情况数，这个可以暴力枚举求解

然后转移就变得比较清晰了：根据转移而来的状态是否包含了第1位来求解

具体转移详见程序

注意arena上交题的时候稍微大一点的数组要开在外面。。。

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

using namespace std;

const int maxd=1000000007,N=100000;

const double pi=acos(-1.0),eps=1e-8;

typedef long long ll;

double f[350][350],dp[350][350][350];

int tim[350][350],m;

struct WheelofFortune{

	double maxExpectedValue(int n,vector<int> s)

	{

		int i,j,k;m=s.size();

		memset(dp,0,sizeof(dp));

		memset(f,0,sizeof(f));

		memset(tim,0,sizeof(tim));

		for (i=1;i<=n;i++)

		{

			for (j=1;j<=i;j++)

			{

				for (k=0;k<i;k++)

				{

					tim[i][(j-k+n-1)%n+1]++;

				}

			}

		}

		f[0][0]=1;

		for (i=1;i<=m;i++)

		{

			for (j=0;j<=i;j++)

			{

				f[i][j]=f[i-1][j]*(n-s[i-1])/n;

				if (j) f[i][j]+=f[i-1][j-1]*s[i-1]/n;

				if (f[i][j]<eps) continue;

				for (k=1;k<=n;k++)

				{

					dp[i][j][k]+=(dp[i-1][j][k]*(n-s[i-1])+(s[i-1]-tim[s[i-1]][k]))/n*f[i-1][j]/f[i][j];

					if (j) dp[i][j][k]+=(dp[i-1][j-1][k]*s[i-1]+tim[s[i-1]][k])/n*f[i-1][j-1]/f[i][j];

				}

			}

		}

		double ans=0.0;

		for (i=0;i<=m;i++)

		{

			double maxnum=0.0;

			for (j=2;j<=n;j++) maxnum=max(maxnum,dp[m][i][j]);

			ans+=f[m][i]*(i+maxnum);

		}

		return ans;

	}

}a;