Woj 1608 - Calculation 状压dp

柔情只为你懂 2022-08-21 14:59 182阅读 0赞

思路来自于武大的一个大神 并不是我的。。。

题目链接：[http://acm.whu.edu.cn/land/problem/detail?problem\_id=1608&contest\_id=16][http_acm.whu.edu.cn_land_problem_detail_problem_id_1608_contest_id_16]

题目大意：给你n个数，让你找它的子集，子集中的数能通过+或-组成s，问这样的子集最多有多少个，任意两个子集不能相交

题目解析：这道题关键是如何枚举子集以及如何判断每个子集能否组成值s，和如何递推

枚举子集其实不难：

for(int i=0; i<=(1<<n)-1; i++)

这样就能枚举所有子集

要判断子集能否组成s，就要枚举子集的子集

for(int i=0; i<= ( 1<<n ) - 1; i++)
            { for(int j=(i-1)&i; j; j=(j-1)&i) { }
            }

在这里j就是i的子集，因为j枚举了所有比i小的数，且和i做了位与运算，能保证j肯定是i的子集。

如果懂了上面，递推就很简单了

我们知道一个集合j的任意子集s的最优解

只要枚举j的子集，判断哪两个子集相加最大就是集合j的最优解

代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    int main()
    {
        int t;
        RI(t);
        while(t--)
        {
            int n,s;
            RII(n,s);
            int a[15];
            int mark[1<<n];
            int ans[1<<n];
    
            for(int i=0; i<n; i++)
                RI(a[i]);
            int sum[1<<n];
            for(int i=0; i<=(1<<n)-1; i++)
            {
                sum[i]=0;
                for(int j=0; j<n; j++)
                    if((i>>j)&1) sum[i]+=a[j];
            }
    
    
            for(int i=0; i<= ( 1<<n ) - 1; i++)
            {
                mark[i]=(sum[i]==s);
                for(int j=(i-1)&i; j; j=(j-1)&i)
                {
                    mark[i]|=(sum[j]+s==sum[i-j]||sum[j]-s==sum[i-j]);
                }
            }
    
            for(int i=0; i<=(1<<n)-1; i++)
            {
                ans[i]=mark[i];
                for(int j=i&(i-1); j; j=(j-1)&i)
                {
                    ans[i]=max(ans[i],ans[j]+ans[i-j]);
                }
            }
    
            cout<<ans[(1<<n)-1]<<endl;
    
        }
    
        return 0;
    }

[http_acm.whu.edu.cn_land_problem_detail_problem_id_1608_contest_id_16]: http://acm.whu.edu.cn/land/problem/detail?problem_id=1608&contest_id=16