HDU 4901 DP双肩包

HDU 4901 DP背包

给你n个数，问你将数分成两个数组，S，T ，T 中所有元素的需要都比S任意一个大，问你S中所有元素进行 XOR 操作和 T 中所有元素进行 &操作值相等的情况有多少种。

DP背包思路

dpa[i][j][0]  表示从左开始到i，不取i，状态为j的方案数

dpa[i][j][1]  表示从作开始到i，取i，状态为j的方案数

dpb[i][j]      表示从右开始到i，状态为j的方案数

因为S集合一定在T集合的左边，那么可以枚举集合的分割线，并且枚举出的方案要保证没有重复，如果要保证不重复，只要保证分割线上的点要强制被取到就行了。最后计算时候，用dpa[i][j][1]使左边强制取到分割线。

#include "stdio.h"
#include "string.h"
__int64 mod=1000000007;
__int64 dpa[1010][1025][2],dpb[1010][1025],a[1010];
int main()
{
    int Case,n,i,j;
    __int64 ans;

    scanf("%d",&Case);
    while (Case--)
    {
        scanf("%d",&n);
        for (i=1;i<=n;i++)
            scanf("%I64d",&a[i]);
        memset(dpa,0,sizeof(dpa));
        memset(dpb,0,sizeof(dpb));
        dpa[1][a[1]][1]=1;
        for (i=2;i<=n;i++)
        {
            dpa[i][a[i]][1]++;
            for (j=0;j<1024;j++)
            {

                dpa[i][j][0]+=(dpa[i-1][j][0]+dpa[i-1][j][1])%mod;
                if (dpa[i][j][0]>mod) dpa[i][j][0]-=mod;

                dpa[i][j^a[i]][1]+=(dpa[i-1][j][1]+dpa[i-1][j][0])%mod;
                if (dpa[i][j^a[i]][1]>mod) dpa[i][j^a[i]][1]-=mod;
            }
        }
        dpb[n][a[n]]=1;

        for (i=n-1;i>=1;i--)
        {
            dpb[i][a[i]]++;
            for (j=0;j<1024;j++)
            {

                dpb[i][j&a[i]]+=dpb[i+1][j];
                if (dpb[i][j&a[i]]>mod) dpb[i][j&a[i]]-=mod;

                dpb[i][j]+=dpb[i+1][j];
                if (dpb[i][j]>mod) dpb[i][j]-=mod;
            }
        }
        ans=0;

        for (i=1;i<n;i++)
            for (j=0;j<=1024;j++)
            {
                ans+=(dpa[i][j][1]*dpb[i+1][j])%mod;
                if (ans>mod)ans-=mod;
            }
        printf("%I64d\n",ans);
    }
    return 0;
}