HDU--5119Happy Matt Friends+dp

其实还是穷举子集类的dp,一般这种dp我们只需要用一个一维的滚动数组就可以了,但是这个题目状态转移的时候不但可能向后还有可能向前,所以这次得用二维数组.
状态方程 dp[i][j]=dp[i-1][j]+dp[i-1][j^num[i]],分别表示第i个数不取和第i个数取情况下状态.

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 2100000  ///太小就会WA

int  dp[50][maxn];
int num[50];

int main()
{
     int t,Case=0;
     scanf("%d",&t);
     while(t--)
     {
           int n,m;
           memset(dp,0,sizeof(dp));
           scanf("%d%d",&n,&m);
           for(int i=1;i<=n;i++)
                scanf("%d",&num[i]);
          int Max=(1<<20);
          dp[0][0]=1;
          ///利用j^num[i]^num[i]=j进行状态转移
          ///即dp[i-1][j]是由dp[i-1][j^num[i]]再^num[i]得到的
          ///dp[i][j]=dp[i-1][j]+dp[i-1][j^num[i]]
           for(int i=1;i<=n;i++)
           {
               for(int j=0;j<=Max;j++)
                   dp[i][j]=dp[i-1][j]+dp[i-1][j^num[i]];
            }
           long long sum=0;
           for(int i=m;i<=Max;i++)
                sum+=dp[n][i];
            printf("Case #%d: %lld\n",++Case,sum);
     }
 return 0;
}