题意:

曾经有个人叫苏格拉底..他让你在一片田地里选麦子..

这块地里有n个麦子,大小都不同,你能记住你所遇到的每个麦子的大小..

你只能选一次麦子

求最优策略下选到那个最大的麦子的概率

解法:

1,我们假设我们看了前i个麦子

第i+1个麦子如果比前i个都大,那么它是最大的概率为(i+1)/n

证明的话..(其实这是说明不是证明)

我们假设随机分配,那么在每个位置的概率都是1/n

然而..我们已经知道第i+1个是前i+1个里面最大的,所以它集合了前i+1个是最大的可能性..

**证明:如果n在这个位置,那么一共有(n-1)!种排列姿势

然而第i+1个是前i个里面最大的排列姿势是

[tex]C_n^{i+1}*P^i_i*P^{n-(i+1)}_{n-(i+1)}[/tex]
[tex]= \frac{n!} {(i+1)! * (n-(i+1))!} * i! * (n-(i+1))![/tex]
[tex]= n! / (i+1)[/tex]

所以 (n-1)! / (n!/(i+1)) = (i+1/n)

2,我们选择i,对于前i个全部扔掉,之后选第一个比前i个都大的数,一定是一种最优解法

根据第一条,我们可以知道前i个的大小顺序基本无关..

唯一有关的是会不会之前就选掉..这个东西我们判定一下

之前的最大值在前j个数里面,是前i个中的一个的概率是i/j

没啦..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    freopen("princess.in","r",stdin);
    freopen("princess.out","w",stdout);
    int n;
    scanf("%d",&n);
    #ifdef absi2011
    for (;n!=-1;)
    {
    #endif
    int i;
    double max_ans=(double)1/n;
    for (i=1;i<=n;i++)
    {
        int j;
        double ans=0;
        for (j=i+1;j<=n;j++)
        {
            ans+=((double)1/n)*((double)i/(j-1));
        }
        max_ans=max(max_ans,ans);
    }
    printf("%.12lf\n",max_ans);
    #ifdef absi2011
        scanf("%d",&n);
    }
    #endif
    return 0;
}