[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;
}