首页 > 代码库 > HDU 4336 Card Collector (期望DP+状态压缩 或者 状态压缩+容斥)
HDU 4336 Card Collector (期望DP+状态压缩 或者 状态压缩+容斥)
题意：有N(1<=N<=20)张卡片，每包中含有这些卡片的概率，每包至多一张卡片，可能没有卡片。求需要买多少包才能拿到所以的N张卡片，求次数的期望。
析：期望DP，是很容易看出来的，然后由于得到每张卡片的状态不知道，所以用状态压缩，dp[i] 表示这个状态时，要全部收齐卡片的期望。
由于有可能是什么也没有，所以我们要特殊判断一下。然后就和剩下的就简单了。
另一个方法就是状态压缩+容斥，同样每个状态表示收集的状态，由于每张卡都是独立，所以，每个卡片的期望就是1.0/p，然后要做的就是要去重，既然要去重，
那么就是得用容斥原理了。
代码如下：
期望DP+状态压缩
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
//#include <tr1/unordered_map>
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
//using namespace std :: tr1;
typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = (1<<20) + 5;
const LL mod = 10000000000007;
const int N = 1e6 + 5;
const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1};
const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
inline LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a%b); }
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a < b ? a : b; }
inline int Max(int a, int b){ return a > b ? a : b; }
inline LL Min(LL a, LL b){ return a < b ? a : b; }
inline LL Max(LL a, LL b){ return a > b ? a : b; }
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
double dp[maxn];
double p[25];
int main(){
while(scanf("%d", &n) == 1){
double pp = 1.0;
for(int i = 0; i < n; ++i){
scanf("%lf", p+i);
pp -= p[i];
}
dp[(1<<n)-1] = 0.0;
for(int i = (1<<n)-2; i >= 0; --i){
double have = 0.0, sum = 1.0;
for(int j = 0; j < n; ++j)
if(i&(1<<j)) have += p[j];
else sum += p[j] * dp[i|(1<<j)];
dp[i] = sum / (1.0 - pp - have);
}
printf("%.4f\n", dp[0]);
}
return 0;
}
状态压缩+容斥
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
//#include <tr1/unordered_map>
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
//using namespace std :: tr1;
typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const LL LNF = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = (1<<20) + 5;
const LL mod = 10000000000007;
const int N = 1e6 + 5;
const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1};
const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
inline LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a%b); }
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a < b ? a : b; }
inline int Max(int a, int b){ return a > b ? a : b; }
inline LL Min(LL a, LL b){ return a < b ? a : b; }
inline LL Max(LL a, LL b){ return a > b ? a : b; }
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
double p[25];
int main(){
while(scanf("%d", &n) == 1){
for(int i = 0; i < n; ++i) scanf("%lf", p+i);
double ans = 0.0;
for(int i = 1; i < (1<<n); ++i){
int cnt = 0;
double sum = 0.0;
for(int j = 0; j < n; ++j) if(i&(1<<j)){
sum += p[j];
++cnt;
}
ans += (cnt & 1) ? 1.0/sum : -1.0/sum;
}
printf("%f\n", ans);
}
return 0;
}
HDU 4336 Card Collector (期望DP+状态压缩 或者 状态压缩+容斥)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。