 /**//*
n<=50张卡 如3张:+1 ,-2 , *3 其排列有
0 + 1 - 2 * 3 = -5
0 + 1 * 3 - 2 = 1
0 - 2 + 1 * 3 = 1
0 - 2 * 3 + 1 = -5
0 * 3 + 1 - 2 = -1
0 * 3 - 2 + 1 = -1
期望为-1.6666666666666667
求给定的n张卡的期望值

看解题报告http://www.topcoder.com/wiki/display/tc/TCO'10+Wildcard+Round
以及bmerry代码的

不可能n!的枚举
设+、-卡共有s张
按照一个+、-卡后接连续的*卡分类,则有s部分,其全排列不影响期望(总共s!种,但期望都一样)
所以只考虑无序的(无序可以用默认的一种顺序,即卡出现的先后顺序,或者说编号)
***a1***a2*** as***
***表示*卡
由于是等概率的,所以总体来统计,每个+、-卡都会接同样的*卡,
既然每张+、-卡情况一样,那就考虑a1卡
其后会接0,1 ,m张*卡
答案就是 sum * (0,1, m)张*卡的期望 sum = ∑ai
求k张*卡的期望可以用dp做
看bmerry代码的做法,解题报告的麻烦一点吧
一开始只有s张a卡排着,然后插入一张张*卡
dp[i,j]表示插入了前面i张*卡,a1后接j张*卡,它们构成的期望值
分第i张卡插不插入到a1之后构成j张连续的*卡,概率为 该插入的位置/总位置
dp[i,j] =
dp[i-1,j] * (n-j-1)/n
+ m[i]*dp[i-1,j-1] * j/n
n为s+i

这道题一个很好的想法就是答案为sum * (0,1, m)张*卡的期望 sum = ∑ai !!!!!!
而求后接k张*卡的期望,bmerry的做法是一张一张卡插入,然后求得期望
小规模到大规模,通过考虑插入位置来实现,这个做法应该较好
*/
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<cstring>
#include<string>

using namespace std;

 class CalculationCards {

public:

 double getExpected(vector <string> cards) {
vector<int> mults;
int sum = 0;
 for(vector <string>::iterator it = cards.begin() ; it != cards.end() ; it++) {
string str = *it;
if(str[0] == '*')
mults.push_back(str[1]-'0');
else sum += atoi(str.c_str());
}

int m = mults.size() , n = cards.size() - m;
cout<<m<<" "<<n<<" "<<sum<<endl;

//dp[i,j]前面i个mul选j个的期望
 double dp[60][60] = {0.0};
dp[0][0] = 1.0;
 for(int i = 1 ; i <= m ; i++) {
cout<<i<<":\n";
n++;
dp[i][0] = dp[i-1][0]*(n-1)/n;
cout<<dp[i][0];
for(int j = 1; j <= i ; j++)
 {
dp[i][j] =
dp[i-1][j]*(n-j-1)/n
+ mults[i-1]*dp[i-1][j-1]*j/n;
cout<<" "<<dp[i][j];
}
cout<<endl;
}

double tot = 0;
for(int k = 0 ; k <= m ; k++)
tot += dp[m][k];
return sum * tot;
}

};

|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|