Hdu 4336 Card Collector （狀態概率DP|容斥原理）
詳細的題目大意與解析大家參考一下kuangbin的文章。
kuangbin鏈接
這邊說一下自己對於kuangbin代碼以及容斥原理位元素枚舉的理解與解釋，希望對大家有所幫助。
狀態DP AC代碼：狀態壓縮的思想我就不贅述了，我也只是略懂，這邊僅僅分析一下狀態方程
由於量比較多，我這邊有的便用文字代替，有利於描述。
dp[i]表示i狀態達到滿狀態（即收集滿n個物品，以下稱滿狀態）所需要的期望。
那麼i狀態當中收集了x的物品，剩余n-x個物品沒有收集
那麼dp[i]=p*dp[i]+p2*dp[i2]+1；
這邊解釋一下上面的變量：
p表示的是假如下一次抽到的物品是已經搜集過的物品被抽到的概率之和，至於為什麼要這樣子，有概率DP基礎的應該知道吧？狀態分解，事件之和。
p2表示的是抽到沒有收集過物品的概率，已經加上該物品之後的狀態要達到滿狀態的期望，這邊少了一個累加，所有沒有收集的累加。依然依據的是狀態的分解和事件之和。
假如有問題的話，歡迎評論指教。
#include
#include
#include
using namespace std;
double dp[1 << 22];
double p[22];
int main()
{
int n;
while (cin >> n)
{
double op = 0;
for (int i = 0; i = 0; i--)
{
double x = 0, sum = 1;
for (int j = 0; j < n;j++)
if (i&(1 << j)) x += p[j];
else sum += p[j] * dp[i|(1 << j)];
dp[i] = sum / (1 - op - x);
}
printf("%.5lf\n", dp[0]);
}
}
容斥原理應用：位運算枚舉
這邊可能你需要百度一下容斥原理是怎麼一個東西，再回來看我的解釋會比較清楚，因為容斥原理我也不知道怎麼講才清楚，這邊提供一個別人推薦的文章。容斥原理
好了，現在你可能已經懂了什麼是容斥原理。
那麼這邊我以n=3為例。並且按照狀態壓縮來講解。
我現在是要得到111的
那麼1/p1（p1表示的是事件1發生的概率）表示的是1發生的概率，這邊包括001,011,111,101
同理,1/p2包括的是010,011,111,110
1/p3：100,101,111,110
將三個相加，所得到的便是狀態001,010,100,011*2,101*2,110*2,111*3這些狀態對應的期望.我們需要的是111狀態，所以需要想辦法減去其他的
1/(p2+p1)包括,011,010,001,111,110,101
1/(p2+p3)包括110,100,010,111,101,011
1/(p3+p1)包括101,001,100,111,011,110
1/(p1+p2+p3)包括001,010,100,110,011,101,111
根據容斥原理，減去上面三個，得到：（全是負的）001,010,100,110,011,101
所以最後再加上一個1/(p1+p2+p3)即得到111狀態對應的期望。
1/p對應的是期望，希望大家好好理解，我也是看了很久，有問題的歡迎跟我交流哈。QQ：417033420
#include
#include
#include
#include
using namespace std;
double p[22];
int main()
{
int n;
while (scanf("%d", &n) == 1)
{
for (int i = 0; i
