Topcoder SRM 656 (Div.1) 250 RandomPancakeStack - 概率+记忆化搜索

2023-01-01 10:07:05

最近连续三次TC爆零了，，，我的心好痛。

不知怎么想的，这题把题意理解成，第一次选择j，第二次选择i后，只能从1~i-1、i+1~j找，其实还可以从j+1~n中找，只要没有被选中过就行。。。

【题意】

给出n个蛋糕，第i个蛋糕的宽度是i，每个蛋糕有一个娱乐值d[i]，（题目中是从0开始的，我这里暂时视为从1开始）一开始从所有蛋糕中等概率拿出一个蛋糕，设它的宽度为k。

接下来，等概率地从剩余蛋糕中选择，【1】如果选出的蛋糕宽度大于K，则终止选择，【2】如果小于K，则继续以同样的方法等概率地在剩余的蛋糕中选择。。直到不能再选择或者选择终止为止。

求所选出的蛋糕娱乐和的期望。

【解】

设dp[now][cur]为剩余n个蛋糕，并且上一次选择是cur+1，即选择1~cur会发生上边【2】的情况。

那么dp[now][cur]=sigema( (dp[now-1][i-1]+a[i])/now ) (1<=i<=cur) ，就是选中i后剩下now-1个蛋糕，下次可选的是前i-1个蛋糕

写成记忆化搜索也可以，直接枚举也可以（貌似记忆化搜索更容易想）。

#include<bits/stdc++.h>

#define eps 1e-9

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define FOR(i,j,k) for(int i=j;i<=k;i++)

#define MAXN 1005

#define MAXM 40005

#define INF 0x3fffffff

using namespace std;

typedef long long LL;

int i,j,k,n,m,x,y,T,ans,big,cas,num;

bool flag;

double dp[][];

bool vis[][];

int a[];

class RandomPancakeStack

{

        public:

        double dfs(int n,int cur)//n个剩余，可选1~cur

        {

            if (vis[n][cur]) return dp[n][cur];

            vis[n][cur]=;

            dp[n][cur]=;

            for (i=;i<=cur;i++)

            {

                dp[n][cur]+=(dfs(n-,i-)+a[i])/n;

            }

            return dp[n][cur];

        }

        double expectedDeliciousness(vector <int> d)

        {

            int n=d.size();

            memset(vis,,sizeof(vis));

            for (i=;i<n;i++) a[i+]=d[i];

            return dfs(n,n);

        }

};

附上题目：

Problem Statement

Charlie has N pancakes. He wants to serve some of them for breakfast. We will number the pancakes 0 through N-1. For each i, pancake i has width i+1 and deliciousness d[i].

Charlie chooses the pancakes he is going to serve using the following randomized process: He starts by choosing the first pancake uniformly at random from all the pancakes he has. He places the chosen pancake onto a plate. This pancake now forms the bottom of a future stack of pancakes. Then, Charlie repeats the following procedure:

If there are no more pancakes remaining, terminate.
Choose a pancake uniformly at random from the pancakes that have not been chosen yet.
If the width of this pancake is greater than the width of the pancake on top of the stack, terminate without taking it.
Place the chosen pancake on top of the stack and go back to step 1.

You are given the vector <int> d with N elements. The total deliciousness of a serving of pancakes is the sum of the deliciousness of all pancakes used in the serving. Compute and return the expected value of the total deliciousness of the pancakes chosen by Charlie.

Definition

Class:	RandomPancakeStack
Method:	expectedDeliciousness
Parameters:	vector <int>
Returns:	double
Method signature:	double expectedDeliciousness(vector <int> d)
(be sure your method is public)

Limits

Time limit (s):	2.000
Memory limit (MB):	256
Stack limit (MB):	256

Notes

Your return value must have an absolute or relative error smaller than or equal to 1e-6

Constraints

The number of elements in d will be between 1 and 250, inclusive.

Each element of d will be between 1 and 1,000, inclusive.

Examples

{1,1,1}

Returns: 1.6666666666666667

The following scenarios may occur:

With probability 1/3, Charlie chooses pancake 0 first. In this case he won't be able to add any more pancakes and the total deliciousness of his serving of pancakes will be 1.
With probability 1/3, Charlie chooses pancake 1 first. What happens in the second round? With probability 1/2 he will choose pancake 0 and with probability 1/2 it will be pancake 2. In the first case the total deliciousness of Charlie's pancakes will be 2, in the second case it will be 1.
With probability 1/3, Charlie chooses pancake 2 first. If he chooses pancake 0 next, the total deliciousness of his pancakes will be 2. If he happens to choose pancake 1 next (followed by pancake 0 in the third round), the total deliciousness will be 3.

Summing this up, we get the expected deliciousness to be 1/3 * (1) + 1/3 * (1/2 * 1 + 1/2 * 2) + 1/3 * (1/2 * 2 + 1/2 * 3) = 5/3 = 1.666...

{3,6,10,9,2}

Returns: 9.891666666666667

{10,9,8,7,6,5,4,3,2,1}

Returns: 10.999999724426809

{1,2,3,4,5,6,7,8,9,10}

Returns: 7.901100088183421

{2,7,1,8,2,8,1,8,2,8,4,5,90,4,5,2,3,5,60,2,8,74,7,1}

Returns: 19.368705050402465

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

Returns: 1.718281828459045

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.