Card Collector HDU - 4336

来源:http://www.cnblogs.com/hehe54321/archive/2017/10/07/hdu-4336.html
-Advertisement-
Play Games

Card Collector HDU - 4336 ans[S]表示獲得S的卡片次數的期望考慮到達S前一次的卡片1.獲得一張已獲得的 期望是ans[S]*sum{p[i]|i在S中}2.獲得一張未獲得的 期望是sum{ans[S-i]*p[i]|i在S中}3.未獲得卡片 期望是ans[S]*p[0] ...


Card Collector HDU - 4336

ans[S]表示獲得S的卡片次數的期望
考慮到達S前一次的卡片
1.獲得一張已獲得的 期望是ans[S]*sum{p[i]|i在S中}
2.獲得一張未獲得的 期望是sum{ans[S-i]*p[i]|i在S中}
3.未獲得卡片 期望是ans[S]*p[0]
因此ans[S]=ans[S]*(p[0]+sum{p[i]|i在S中})+sum{ans[S-i]*p[i]|i在S中}
ans[S]*(1-p[0]-sum{p[i]|i在S中})=sum{ans[S-i]*p[i]|i在S中}
ans[S]=sum{ans[S-i]*p[i]|i在S中}/(1-p[0]-sum{p[i]|i在S中})

X=ans[S]
Y=sum{(ans[S-i]+1)*p[i]|i在S中} 即獲得一個未得的卡對期望的貢獻
P2=p[0]+sum{p[i]|i在S中}) 即獲得已得的卡或無卡的概率
那麼Y+P2*(X+1)=X
P2*X+P2+Y=X
P2+Y=(1-P2)*X
X=(P2+Y)/(1-P2)

ans[S]表示全0到S所用步數的期望
考慮到達S前一次的卡片
1.未獲得卡片/獲得一張已獲得的卡片 期望是(p[0]+sum{p[S的某一個]})*(ans[S]+1)
01 0.6x+0.6 10 0.9x+0.9
2.獲得一張未獲得的 期望是sum{p[S的某一個]*(ans[S-S的某一個]+1)}
01 0.1 10 0.4(錯誤答案花費7個小時)

以上全部都是錯的。直覺上會讓人想到將ans[S]定義為獲得S的卡片的購買包數的期望,然而由於即使一包也不買,這個期望也不為0,導致非常難處理。

更好的方法是定義ans[S]為獲得S的卡片到全部獲得所用步數的期望。p[0]表示買一包不獲得卡片的概率。考慮S狀態後下一步:

1.未獲得卡片/獲得一張已獲得的卡:期望是$(p[0]+sum\{p[S的某一個]\})*(ans[S]+1)$

樣例1:0.9*11=9.9
樣例2:

10 (0.5+0.4)*(ans[2]+1)
01 (0.5+0.1)*(ans[1]+1)
00 (0.5)*(ans[0]+1)

2.獲得一張未獲得的:期望是$sum\{p[S以外的i]*(ans[S+i]+1)\}$

樣例1:0.1*1=0.1
樣例2:
10 0.1*1=0.1
ans[2]=10
01 0.4*1=0.4
ans[1]=2.5
00 0.1*(ans[1]+1)+0.4*(ans[2]+1)=4.75
ans[0]=10.5

$(p[0]+sum\{p[S的某一個]\})*(ans[S]+1)+sum\{p[S以外的i]*(ans[S+i]+1)\}=ans[S]$

$(p[0]+sum\{p[S的某一個]\})*ans[S]+p[0]+sum\{p[S的某一個]\}+sum\{p[S以外的i]*(ans[S+i]+1)\}=ans[S]$

$(1-(p[0]+sum{p[S的某一個]}))*ans[S]=p[0]+sum{p[S的某一個]}+sum{p[S以外的i]*(ans[S+i]+1)}$

$ans[S]=(p[0]+sum\{p[S的某一個]\}+sum\{p[S以外的i]*(ans[S+i]+1)\})/(1-(p[0]+sum\{p[S的某一個]\}))$

 1 #include<cstdio>
 2 #include<cstring>
 3 double p[22],ans[1100000],tt;
 4 int n;
 5 int main()
 6 {
 7     int i,j;
 8     while(scanf("%d",&n)==1)
 9     {
10         p[0]=0;
11         for(i=1;i<=n;i++)
12         {
13             scanf("%lf",&p[i]);
14             p[0]+=p[i];
15         }
16         p[0]=1-p[0];
17         memset(ans,0,sizeof(ans));
18         for(i=(1<<n)-2;i>=0;i--)
19         {
20             tt=p[0];
21             for(j=1;j<=n;j++)
22                 if(i&(1<<(j-1)))
23                     tt+=p[j];
24                 else
25                     ans[i]+=p[j]*(ans[i|(1<<(j-1))]+1);
26             ans[i]+=tt;
27             ans[i]/=(1-tt);
28         }
29         printf("%lf\n",ans[0]);
30     }
31     return 0;
32 }

http://blog.csdn.net/a1061747415/article/details/34481361

http://www.cnblogs.com/six-god/p/3580242.html


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Too Rich Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1410 Accepted Submission(s): 362 Probl ...
  • SpringBoot引入JPA,application.ymlapplication.yml增加資料庫鏈接參數,啟動卡死,日誌沒有動,如下圖 折騰好久,後面發現用 Maven的package 過程中 可以看出資料庫名稱出錯,如下圖 這時候再啟動,發現控制台日誌也有了看出資料庫名稱出錯。 最後實驗下, ...
  • 最近需要做一個粗略的後臺管理的許可權,根據用戶的等級來載入相應的菜單,控制到子菜單。使用的是Easyui這個框架。 1.我使用的mysql資料庫。在這裡我就建立四張表,角色表(tb_users),菜單表(tb_menu),用戶許可權表(tb_role),許可權菜單表(tb_user_role).表結構如下 ...
  • 在 java平臺上,lombok 提供了簡單的註解的形式來幫助我們消除一些必須有但看起來很臃腫的代碼, 比如屬性的get/set,及對象的toString等方法,特別是相對於 POJO。簡單的說,就是簡化了Java代碼,消除Java冗長的代碼。lombok jar的下載地址:https://proj ...
  • 把泛型由Boolean改為String。 ...
  • RBAC --> 基於角色的許可權控制 tb_user tb_role tb_userrole tb_menu(增、刪、改、查) tb_rolemenu 1 說明 給出三個頁面:index.jsp、user.jsp、admin.jsp。 index.jsp:誰都可以訪問,沒有限制; user.jsp: ...
  • 題目鏈接 Problem Description You have got a cylindrical cup. Its bottom diameter is 2 units and its height is 2 units as well.The height of liquid level i ...
  • 是的,我是想到什麼知識點就說什麼,沒有固定的主題,我的標題都是在寫完博客再給的。本篇博文說說列表進階話題。其實列表應該是比較熟悉的了,而毫不誇張的說,在實際的開發中,列表也是使用的最多的,以後你會體會到我說的這句話的。 列表解析 1.什麼是列表解析: 根據已有列表,高效生成新列表的方式,還有另一個叫 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...