Codechef 12.5 LEBOXES meet-in-the-middle+DP
题目大意：
有$n$个箱子，第$i$个箱子打开之后有$\frac{P_i}{100}$的概率得到$V_i$单位的钱，有$1-\frac{P_i}{100}$的概率得到$1$个钻石。还有$m$个物品，购买第$i$个物品需要花费$C_i$个单位的钱以及$D_i$个钻石。现在打开所有的箱子，求最多能够买到物品数目的期望值。
数据范围：$n,m\leq{30},1\leq{V_i,C_i}\leq{10^7},0\leq{D_i}\leq{30},0\leq{P_i}\leq{100}$。
算法讨论：
我们不妨先利用DP预处理出$f_{i,j}$表示想买$i$个物品的时候，如果得到了$j$个钻石，那么最少还需要多少单位的钱。
考虑到$n$非常小，利用Meet in the middle，将所有箱子划分成两个尽可能大小相同的集合，依次在集合内部$2^n$枚举所有可能的情况，并存下在每个集合内得到固定数量的钻石的时候得到的钱数从小到大的排序。
我们枚举其中一个集合的所有可能情况，枚举另一个集合得到了多少个钻石，再枚举最终能得到多少物品，对于一个物品数，在另一个集合固定钻石数的所有情况中，钱数是一段连续区间，我们可以通过二分得到这段区间，在预处理时维护概率的前缀和就能用这段区间的概率和更新答案。
时空复杂度：
时间复杂度$O(nm^2+\lfloor\frac{n}{2}\rfloor{2^{\lfloor\frac{n}{2}\rfloor}}+2^{\lfloor{\frac{n}{2}}\rfloor}nm{\lfloor\frac{n}{2}\rfloor})$，空间复杂度$O(nm+2^{\lfloor\frac{n}{2}\rfloor})$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef double ldb;
int v[30], p[30], c[30], d[30];
int f[2][31][31];
vector<pair<int, ldb> > rset[16];
vector<int> r_v[16];
vector<pair<int, pair<int, ldb> > > all_lset;
vector<ldb> r_sump[16];
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
int T;
cin >> T;
int n, m, i, j, k, now, last;
while (T--) {
cin >> n >> m;
for (i = 0; i < n; ++i)
cin >> v[i] >> p[i];
for (i = 0; i < m; ++i)
cin >> c[i] >> d[i];
now = 0;
last = 1;
memset(f[now], 0x1f, sizeof f[now]);
f[now][0][0] = 0;
for (i = 0; i < m; ++i) {
swap(now, last);
memset(f[now], 0x1f, sizeof f[now]);
for (j = 0; j <= i + 1; ++j) {
for (k = 0; k <= n; ++k) {
f[now][j][k] = f[last][j][k];
if (k >= d[i] && j)
f[now][j][k] = min(f[now][j][k], f[last][j - 1][k - d[i]] + c[i]);
}
}
}
for (j = 0; j <= m; ++j)
for (k = 1; k <= n; ++k)
f[now][j][k] = min(f[now][j][k], f[now][j][k - 1]);
for (k = 0; k <= n; ++k)
f[now][m + 1][k] = 0x3f3f3f3f;
int half = (n + 1) >> 1;
int total_v, total_dia;
ldb total_p;
all_lset.clear();
for (i = 0; i < (1 << half); ++i) {
total_v = 0;
total_dia = 0;
total_p = 1;
for (j = 0; j < half; ++j) {
if ((i >> j) & 1) {
total_v += v[j];
total_p *= p[j] / 100.0;
}
else {
total_dia++;
total_p *= (100 - p[j]) / 100.0;
}
}
all_lset.push_back(make_pair(total_dia, make_pair(total_v, total_p)));
}
for (i = 0; i <= n - half; ++i) {
rset[i].clear();
r_sump[i].clear();
r_v[i].clear();
}
for (i = 0; i < (1 << (n - half)); ++i) {
total_v = 0;
total_dia = 0;
total_p = 1;
for (j = 0; j < n - half; ++j) {
if ((i >> j) & 1) {
total_v += v[half + j];
total_p *= p[half + j] / 100.0;
}
else {
total_dia++;
total_p *= (100 - p[half + j]) / 100.0;
}
}
rset[total_dia].push_back(make_pair(total_v, total_p));
}
for (i = 0; i <= n - half; ++i) {
sort(rset[i].begin(), rset[i].end());
for (j = 0; j < rset[i].size(); ++j) {
if (!j)
r_sump[i].push_back(rset[i][0].second);
else
r_sump[i].push_back(r_sump[i].back() + rset[i][j].second);
r_v[i].push_back(rset[i][j].first);
}
}
int now_dia, now_v, ins, lastins;
ldb now_p, ans = 0;
for (i = 0; i < all_lset.size(); ++i) {
now_dia = all_lset[i].first;
now_v = all_lset[i].second.first;
now_p = all_lset[i].second.second;
for (j = now_dia; j <= now_dia + n - half; ++j) {
for (k = 1; k <= m + 1; ++k) {
ins = lower_bound(r_v[j - now_dia].begin(), r_v[j - now_dia].end(), f[now][k][j] - now_v) - r_v[j - now_dia].begin();
//if (ins == r_v[j - now_dia].size())
// break;
if (k > 1 && ins) {
if (!lastins)
ans += (k - 1) * now_p * r_sump[j - now_dia][ins - 1];
else
ans += (k - 1) * now_p * (r_sump[j - now_dia][ins - 1] - r_sump[j - now_dia][lastins - 1]);
}
if (ins == r_v[j - now_dia].size())
break;
lastins = ins;
}
}
}
printf("%.4lf\n", (double)ans);
}
return 0;
}
评论 (0)