首页 > 代码库 > poj1322 Chocolate 【 概率DP 】
poj1322 Chocolate 【 概率DP 】
题目链接：poj1322 Chocolate 【概率DP 】
题意：袋中有C种颜色巧克力，每次从其中拿出一块放桌上，如果桌上有两块相同颜色巧克力则吃掉，问取出N块巧克力后，求桌上正好剩下M块巧克力的概率。(已知，若有五种颜色，会发现大部分时间桌上有2或3块巧克力)
题解：我太弱了，看了官方题解：具体优化见代码。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 105;double dp[2][N];int main() { int c, n, m, i, j, cur; while(~scanf("%d", &c), c) { scanf("%d%d", &n, &m); if(m > c || m > n || (n-m)&1) {//考虑奇偶，观察可得 printf("0.000\n"); continue; } if(n > 500) n = 500 - (n&1);//精度要求不高，n较大无影响 memset(dp, 0, sizeof(dp)); dp[0][0] = dp[1][1] = 1.0;//边界 cur = 1;//运算优化，虽然感觉这里效果不大。。 int x = n-1; for(i = 2; i <= n; ++i) { dp[1-cur][0] = dp[cur][1] / c; dp[1-cur][c] = dp[cur][c-1] / c; for(j = 1; j <= i && j < c; ++j) { dp[1-cur][j] = (j+1.0)/c * dp[cur][j+1] + (c-j+1.0)/c * dp[cur][j-1]; } cur = 1-cur; } printf("%.3f\n", dp[n&1][m]); } return 0;}
下面有一个待验证的思路。。。。。。。。。。。挖坑ORZ
//yy：看完题以为纯概率论哇orz。。。我不会DP根本想不到吖。。。
取出n个巧克力后可能有c^n种情况，c种颜色的巧克力各有x1，x2...xc个，Σxi=n
设yi=xi mod 2，桌上剩余巧克力个数M=Σyi
这道题先分n是奇数还是偶数来讨论：
n是偶数的情况下，xi中必须有偶数个是奇数，也就是有偶数个yi=1
所以M可能的取值为0，2，4…2n，2n<c
【当M=k时，也就是说c个yi中一共有k个yi=1，则满足的情况有C(k c)种（从c个yi中选出k个令其为1）】
【总共的情况是C(0 c)+C(2 c)+...+C(2i c)=2^(c-1) 】
n为奇数时同理，则必须有奇数个xi为奇数，也就是奇数个yi=1，M的取值为1，3，...，2n-1
然后用组合数分别求出每种情况的概率就行了。。。。。。。
答案就是C(m,c) / 2^（c-1）
注：上面的情况是n>c。。。
如果n<c，只需把结论的分母变成 C(0 c)+C(2 c)+...+C(n c)即可 (n是偶数的情况)
还不晓得这个思路有没有问题，存不下那么大的组合数，精度问题也解决不了orz…好难啊
poj1322 Chocolate 【 概率DP 】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。