Codechef 12.7 DGCD 数学+树链剖分+线段树
Codechef 12.4 TSUBSTR 后缀自动机+Trie

Codechef 12.5 LEBOXES meet-in-the-middle+DP

shinbokuow posted @ Nov 20, 2015 04:31:36 PM in Something with tags meet-in-the-middle DP , 492 阅读

 

题目大意:
有$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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter