[BZOJ3900]交换茸角 题解

[BZOJ3900]交换茸角 题解

题目地址: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;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据