洛谷P3067《[USACO12OPEN]平衡的奶牛群Balanced Cow Subsets》

三月 02, 2019 4020

Meet in the middle + 状态压缩

题目描述

Farmer John’s owns N cows (2 <= N <= 20), where cow i produces M(i) units of milk each day (1 <= M(i) <= 100,000,000). FJ wants to streamline the process of milking his cows every day, so he installs a brand new milking machine in his barn. Unfortunately, the machine turns out to be far too sensitive: it only works properly if the cows on the left side of the barn have the exact same total milk output as the cows on the right side of the barn!

Let us call a subset of cows “balanced” if it can be partitioned into two groups having equal milk output. Since only a balanced subset of cows can make the milking machine work, FJ wonders how many subsets of his N cows are balanced. Please help him compute this quantity.

给n个数，从中任意选出一些数，使这些数能分成和相等的两组。

求有多少种选数的方案。

输入输出格式

输入格式：

  • Line 1: The integer N.

  • Lines 2..1+N: Line i+1 contains M(i).

输出格式：

  • Line 1: The number of balanced subsets of cows.

输入输出样例

输入样例#1

1
2
3
4
5
4 
1 
2 
3 
4

输出样例#1

1
3

说明

There are 4 cows, with milk outputs 1, 2, 3, and 4.

There are three balanced subsets: the subset {1,2,3}, which can be partitioned into {1,2} and {3}, the subset {1,3,4}, which can be partitioned into {1,3} and {4}, and the subset {1,2,3,4} which can be partitioned into {1,4} and {2,3}.

解题思路

先看一眼数据范围

对于每一个数，有三种状态：

  • 放在左边的集合里
  • 放在右边的集合里
  • 不选

好，一个 O(3^n) 的算法就出来了
但是过不去

考虑优化
可用 Meet in the middle 进行优化

对两个区间 [1, \frac{n}{2}] 和 [\frac{n}{2} + 1, n] 分别搜索，时间复杂度降为 O(3^{\frac{n}{2}}) ，或者说 O(\sqrt{(3^n)})

合并答案这部分我在学的时候也不大理解

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <algorithm>
#include <iostream>
#include <map>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)
#define _DEBUG(x) std::cerr << #x << " = " << x << std::endl;

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 20 + 10;
const int FIXED_N = 20 + 1;

struct S {
    int sum;
    int status;
    
    S() { sum = status = 0; }
} cca[(1 << FIXED_N)], ccb[(1 << FIXED_N)];

int n, a[MAXN], cnta, cntb, ans;
bool uniq[(1 << FIXED_N)];

void Read() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
}

void Search(int l, int r, int sum, int stat, S cc[], int &cnt) {
    if (l > r) {
        cc[++cnt].sum = sum;
        cc[cnt].status = stat;
        return;
    }
    Search(l + 1, r, sum, stat, cc, cnt); // don't choose
    Search(l + 1, r, sum - a[l], stat + (1 << (l - 1)), cc, cnt); // put the cow to set1
    Search(l + 1, r, sum + a[l], stat + (1 << (l - 1)), cc, cnt); // put the cow to set2
}

void mergeAnswer() {
    // double-pointer
    int p1 = 1, p2 = 1;
    while (p1 <= cnta && p2 <= cntb) {
        while (-cca[p1].sum < ccb[p2].sum && p2 <= cntb) ++p2;
        int originalp2 = p2;
        while (p2 <= cntb && -cca[p1].sum == ccb[p2].sum) {
            if (uniq[cca[p1].status | ccb[p2].status] == false) {
                uniq[cca[p1].status | ccb[p2].status] = true;
                ++ans;
            }
            ++p2;
        }
        if (p1 + 1 <= cnta && -cca[p1].sum == -cca[p1 + 1].sum) p2 = originalp2;
        ++p1;
    }
}

bool cmpa(S x, S y) { return x.sum < y.sum; }
bool cmpb(S x, S y) { return x.sum > y.sum; }

int main() {
    IMPROVE_IO();
    Read();
    Search(1, n / 2, 0, 0, cca, cnta);
    Search(n / 2 + 1, n , 0, 0, ccb, cntb);
    std::sort(cca + 1, cca + 1 + cnta, cmpa);
    std::sort(ccb + 1, ccb + 1 + cntb, cmpb);
    mergeAnswer();
    cout << ans - 1 << endl;
    return 0;
}