压缩状态DP位运算

写这个博客的时候刷了一会小视频，今天是各省市基本上都出分了，然后觉得今年的题应该挺难的，评论区有一句话说的挺好的感觉，“起码应该给普通人一条活路啊”，唉…挺惨的，好了，闲话少叙，直接正题！
今天写了一个洛谷，现在的状态是不看题解没有思路，有了思路得写一个多小时，（我太菜了
题目：
https://www.luogu.com.cn/problem/P1441

但是今天没看题解就有了思路，昨天做过类似的题，结果超时+答案部分正确，寄，无奈之下转到题解区，俺想先贴一个 代码，看到这个的时候，我就在想为啥100来行的代码，大佬十来行就能整完，更寄了，唉

#include <bitset>
#include <cstdio>
int w[25];
int table[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
int popcount(unsigned int x) { // 返回x的二进制中1的个数
    int ret = 0;
    for(int i = 0; i < 8; i++) ret += table[x & 15], x >>= 4;
    return ret;
}
int main() {
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", w + i);
    for(int i = 0, li = 1 << n; i < li; i++) {
        if(popcount(i) == n - m) {
            std::bitset<2010> S;
            S[0] = 1;
            for(int j = 0; j < n; j++) if(i & (1 << j)) S |= S << w[j];
            int siz = S.count();
            ans = ans > siz ? ans : siz;
        }
    }
    printf("%d\n", ans - 1);
    return 0;
}
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

以上代码出处：https://www.luogu.com.cn/problem/solution/P1441，pantw为作者
他这个计算位数也比较巧妙，但是应该是大佬的常规操作吧。
重点还是放在循环上
他最关键的是这个语句：

if(i & (1 << j)) S |= S << w[j];
1

这是啥意思，我们可以想一下完全背包问题，就是以下标作为背包重量，这个也是，他是把和作为下标，然后使用位运算标记的，比如说如下例子：

3 1
1 2 2
1
2

显而易见，在拿出2之后1和2可以组成1，2，3所以输出为3
在这时，如果原来的位是S[0]=1,S[1]=1（只有1一个数）然后加进来一个2，用上面的运算，讲S左移两位然后和原来的S相或，这样的话变成了S[0]=1,S[1]=1，S[2]=1,S[3]=1，可能会用疑问，如果加完之后的数和原来重合呢?很简单比如说，原来的状态是S[0]=1,S[1]=1，S[3]=1加进来一个2之后S和S[2]=1,S[3]=1，S[5]=1相或，这样的话就是0，1，2，3，5是1，两个3或完之后变成一个了
一个不太恰当的方法：就是我的方法，我之所以有思路，是因为在这个题之前我做了一个十分类似的题目
https://www.luogu.com.cn/problem/P3694
这里面就是用dp做的，也就是前面的状态累积，然后后面的状态是从前面过来的。（但是都是用位运算，外壳是相同的
但是这个方法就有一个弊端，你再算数量时候，就要知道哪些数字是前面加和已经出现过的，这种的应该把他们删掉，所以就要用向量记载，（我用的数组，如果要用位运算也得要2000多位，在int只有32位的情况下，还是拉倒吧。
所以这个大佬的解决方法还不错，不算是纯的dp，但是方法很巧妙。