http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4100

首先把所有子集的重量和预处理一下,然后用位压缩枚举二叉树,把子树的所有符合题意的结果存到一个vector里面。

(只贴出与题目有关的代码,宏定义见 GitHub

/* 0.019s */
const int mx = 6;

bool vis[1 << mx];
double maxl;
int w[mx], sum[1 << mx];
vector<p2> tree[1 << mx];
#define l first
#define r second

void dfs(int subset)
{
    if (vis[subset]) return;
    vis[subset] = true;
    bool have_children = false;
    int left, right, i, j;
    double d1, d2;
    p2 t(0.0, 0.0);
    for (left = (subset - 1) & subset; left; left = (left - 1) & subset) /// 枚举subset的非空真子集
    {
        have_children = true;
        right = subset ^ left;
        dfs(left), dfs(right);
        d1 = (double)sum[right] / sum[subset];
        d2 = (double)sum[left] / sum[subset]; /// 计算两边的长度
        For(i, tree[left].size()) For(j, tree[right].size())
        {
            t.l = max(tree[left][i].l + d1, tree[right][j].l - d2);
            t.r = max(tree[right][j].r + d2, tree[left][i].r - d1);
            if (t.l + t.r < maxl) tree[subset].PB(t);
        }
    }
    if (!have_children) tree[subset].PB(t);
}

int main()
{
    int n, i, j, root;
    double ans;
    TT
    {
        SD(maxl), SI(n);
        SA(w, i, n);
        For(i, 1 << n)
        {
            sum[i] = 0;
            For(j, n) if (i >> j & 1) sum[i] += w[j];
            tree[i].clear();
        }
        mem(vis, 0);
        dfs(root = (1 << n) - 1);
        ans = -1;
        For(i, tree[root].size()) Qmax(ans, tree[root][i].l + tree[root][i].r);
        PD(ans);
    }
    return 0;
}

Comments

comments powered by Disqus