题目地址：BZOJ：Problem 3900. — 交换茸角

题目描述

动物园里有 n 头麋鹿。每头麋鹿有两支茸角，每支茸角有一个重量。然而，一旦某头麋鹿上两支茸角的重量之差过大，这头麋鹿就会失去平衡摔倒。为了不然这种悲剧发生，动物园院长决定交换某些茸角，使得任意一头麋鹿的两角重量差不超过 c。然而，交换两支茸角十分麻烦，不仅因为茸角需要多个人来搬运，而且会给麋鹿造成痛苦。因此，你需要计算出最少交换次数，使得任意一头麋鹿的两角重量差不超过 c。
注意，交换两支茸角只能在两头麋鹿之间进行。因为交换同一头麋鹿的两支角是没有意义的。

输入输出格式

输入格式：
第一行为整数 n,c。接下来 n 行，每行两个整数，分别表示一开始每头麋鹿的两角重量。

输出格式：
一个数，即最少交换次数。如果无论如何也不能使每头麋鹿平衡，输出 -1。

输入输出样例

输入样例#1：

3 0
3 3
2 5
2 5

输出样例#1：

1

说明

对于 100% 的数据，n <= 16, c <= 1000000, 每支茸角重量不超过 1000000。

题解

这个n的范围看起来很像状压DP，那我们就往那个方向去想。
我们考虑用状压表示子集，dp[S]表示S集合中的所有鹿换角最少多少次能满足条件。对于初始值，我们把S集合中的鹿的所有角都拿出来排个序分好组，如果发现有一组角的差值大过c，那么这个集合内部就无法自行调整为满足条件的情况，dp值应设置为INF。如果集合内部已经满足条件，dp值应设置为0。如果都不是上面的情况，那么按照最差的换法，应该是每个鹿从待选角中找到配对的角换上，这个次数最差是集合内鹿的数量-1的，dp值应设置为这个最差的值。
对于转移，我们考虑枚举每个状态S的子集T，有下面的方程
dp[S] = \min(dp[S], dp[T] + dp[S \wedge T])
这个的复杂度是O(2^n \cdot n)的。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 17, INF = 0x3f3f3f3f;

int n, c, a[MAXN], b[MAXN], dp[1 << MAXN];
std::vector<int> tmp;

int main() {
    n = readint();
    c = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        b[i] = readint();
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for(int i = 1; i < (1 << n); i++) {
        bool flag = false;
        tmp.clear();
        for(int j = 1; j <= n; j++) {
            if(i & (1 << (j - 1))) {
                if(std::abs(a[j] - b[j]) > c) flag = true;
                tmp.push_back(a[j]);
                tmp.push_back(b[j]);
            }
        }
        if(!flag) {
            dp[i] = 0;
            continue;
        }
        std::sort(tmp.begin(), tmp.end());
        flag = false;
        for(int j = 0; j < tmp.size(); j += 2) {
            if(tmp[j + 1] - tmp[j] > c) {
                flag = true;
                break;
            }
        }
        if(!flag) dp[i] = tmp.size() / 2 - 1;
    }
    for(int i = 1; i < (1 << n); i++) {
        for(int j = (i - 1) & i; j; j = (j - 1) & i) {
            dp[i] = std::min(dp[i], dp[j] + dp[i ^ j]);
        }
    }
    if(dp[(1 << n) - 1] == INF) {
        printf("-1");
    } else {
        printf("%d", dp[(1 << n) - 1]);
    }
    return 0;
}