ZOJ 2640 Help Me Escape

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

B.Help Me Escape

背景

If thou doest well, shalt thou not be accepted? and if thou doest not well, sin lieth at the door. And unto thee shall be his desire, and thou shalt rule over him.

And Cain talked with Abel his brother: and it came to pass, when they were in the field, that Cain rose up against Abel his brother, and slew him.

And the LORD said unto Cain, Where is Abel thy brother? And he said, I know not: Am I my brother’s keeper?

And he said, What hast thou done? the voice of thy brother’s blood crieth unto me from the ground.

And now art thou cursed from the earth, which hath opened her mouth to receive thy brother’s blood from thy hand;

When thou tillest the ground, it shall not henceforth yield unto thee her strength; a fugitive and a vagabond shalt thou be in the earth.

$ —— Bible Chapter 4$

题面

Now Cain is unexpectedly trapped in a cave with N paths. Due to LORD’s punishment, all the paths are zigzag and dangerous. The difficulty of the ith path is ci.

Then we define f as the fighting capacity of Cain. Every day, Cain will be sent to one of the N paths randomly.

Suppose Cain is in front of the ith path. He can successfully take ti days to escape from the cave as long as his fighting capacity f is larger than ci. Otherwise, he has to keep trying day after day. However, if Cain failed to escape, his fighting capacity would increase ci as the result of actual combat. (A kindly reminder: Cain will never died.)

As for ti, we can easily draw a conclusion that ti is closely related to ci. Let’s use the following function to describe their relationship:

$t_i=\lfloor \frac{1+\sqrt 5}2×c_i^2\rfloor$

After D days, Cain finally escapes from the cave. Please output the expectation of D.

简要翻译

有$n$个妖怪，每个妖怪有一个战斗力$c_j$。小A有一个初始战斗力$f_0$。每天，小A随机选择一个妖怪决斗。设小A在第𝑖天的战斗力为$f_i$。设当前为第$𝑖$天，如果打赢，即$𝑓_i > 𝑐_j$，就可以逃出去，需要花$t_j$天。如果打不赢，小A会让自己变强，$𝑓_{i+1} = 𝑓_i+ 𝑐_j$。求小A逃出来需要的期望天数。

Input

输入包含多组数据。

每组数据包括两行。第一行包含一个$n$和$f$，第二行包含$n$个整数$c_i$。

Output

对于每组数据你要输出期望值，保留小数点后三位。

Sample Input

3 1

1 2 3

Sample Output

6.889

Hint

$n\leq 100$，$f\leq 10,000$，$c_i\leq10,000，1\leq i\leq n$。

用$f(i)$表示战斗力为$i$时，所需要的期望天数。

那么有：若$i>c_j$，则$f(i)=f(i)+\frac 1n(t_j)$；

若（$i\leq c_j$），则$f(i)=f(i)+\frac 1n(f(i+c_j)+1)$。

然后进行记忆化搜索。

Code

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
struct data
{
	int c, t;
};
bool vis[100010];
vector<data> vs;
int N, F;
double dp[100010];
double dfs(int f)
{
	if (vis[f]) return dp[f];
	vis[f] = 1;
	double A = 0;
	for (int i = 0; i < N; ++i)
		if (vs[i].c >= f) A += (1 + dfs(f + vs[i].c)) / N;
		else A += 1.0 * vs[i].t / N;
	return dp[f] = A;
}
int main()
{
	while (~scanf("%d%d", &N, &F))
	{
		vs.clear();
		memset(vis, 0, sizeof(vis));
		for (int i = 0, g; i < N; ++i)
		{
			g = read();
			int p = (1 + sqrt(5)) / 2 * g * g;
			vs.push_back((data) {g, p});
		}
		printf("%.3lf\n", dfs(F));
	}
	return 0;
}