HDU--5119Happy Matt Friends+dp
浏览数：43 /
时间：2015年06月11日
其实还是穷举子集类的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;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
