Woj 1608 - Calculation 狀壓dp

思路來自于武大的一個大神 并不是我的。。。

題目連結：http://acm.whu.edu.cn/land/problem/detail?problem_id=1608&contest_id=16

題目大意：給你n個數，讓你找它的子集，子集中的數能通過+或-組成s，問這樣的子集最多有多少個，任意兩個子集不能相交

題目解析：這道題關鍵是如何枚舉子集以及如何判斷每個子集能否組成值s，和如何遞推

枚舉子集其實不難：

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

這樣就能枚舉所有子集

要判斷子集能否組成s，就要枚舉子集的子集

for(int i=; i<= ( <<n ) - ; i++)
        {
            for(int j=(i-)&i; j; j=(j-)&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=;
const int inf1=-*;
double EPS=;
typedef long long LL;

int main()
{
    int t;
    RI(t);
    while(t--)
    {
        int n,s;
        RII(n,s);
        int a[];
        int mark[<<n];
        int ans[<<n];

        for(int i=; i<n; i++)
            RI(a[i]);
        int sum[<<n];
        for(int i=; i<=(<<n)-; i++)
        {
            sum[i]=;
            for(int j=; j<n; j++)
                if((i>>j)&) sum[i]+=a[j];
        }


        for(int i=; i<= ( <<n ) - ; i++)
        {
            mark[i]=(sum[i]==s);
            for(int j=(i-)&i; j; j=(j-)&i)
            {
                mark[i]|=(sum[j]+s==sum[i-j]||sum[j]-s==sum[i-j]);
            }
        }

        for(int i=; i<=(<<n)-; i++)
        {
            ans[i]=mark[i];
            for(int j=i&(i-); j; j=(j-)&i)
            {
                ans[i]=max(ans[i],ans[j]+ans[i-j]);
            }
        }

        cout<<ans[(<<n)-]<<endl;

    }

    return ;
}