HDU--5119Happy Matt Friends+dp

HDU--5119Happy Matt Friends+dp

其實還是窮舉子集類的dp,一般這種dp我們只需要用一個一維的滾動數組就可以了,但是這個題目狀態轉移的時候不但可能向後還有可能向前,所以這次得用二維數組.
狀態方程 dp[i][j]=dp[i-1][j]+dp[i-1][j^num[i]],分別表示第i個數不取和第i個數取情況下狀態.

代碼如下:

#include
#include
#include
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;
}