3900: 交换茸角

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=3900

思路

状态压缩，f[i]表示只包含i中的所有元素的最小代价
所有元素排序后两两配对都不能满足，就是inf
其他的，一定小于等于元素个数-1
orz wxy

收获

1，知道自己啥都不会
2，子集的子集也是可以到16左右的(4000w)
update:attack证明了，3^n,也就是43046721
3，位运算枚举i的1的子集

for(int j=i;j>0;j=(j-1)&i)

4，常数真的好大

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define dsr ((1<<n)-1)
using namespace std;
const int N=(1<<20)+1;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,c,a[40],b[40];
int f[N];
int calc(int x) {
    vector<int> tmp;
    int js=0;
    for(int i=0;i<n;++i) {
        if(x&(1<<i)) {
            js++;
            tmp.push_back(a[i+1]);
            tmp.push_back(b[i+1]);
        }
    }
    sort(tmp.begin(),tmp.end());
    for(int i=1;i<tmp.size();i+=2) {
        if(tmp[i]-tmp[i-1]>c) {
            return 0x3f3f3f3f;
        }
    }
    return js-1;
}
int main() {
//  freopen("a.in","r",stdin);
    n=read();c=read();
    for(int i=1;i<=n;++i) {
        a[i]=read(),b[i]=read();
    }
    if(calc(dsr)==0x3f3f3f3f) {
        puts("-1");
        return 0;
    }
    for(int i=1;i<=dsr;++i) f[i]=calc(i);
    for(int i=1;i<=dsr;++i) {
        for(int j=i;j>0;j=(j-1)&i) {
            f[i]=min(f[i],f[j]+f[i^j]);
        }
    }
    printf("%d\n",f[dsr]);
    return 0;
}
/*
3 0
3 3
2 5
2 5
*/