首页 > 代码库 > HDU 5119 Happy Matt Friends ——（背包DP）
HDU 5119 Happy Matt Friends ——（背包DP）
题意：有最多40个数字，取任意个数字他们的异或和>=k则是可行的方案，问有多少种可行的方案。
分析：dp[now][j]表示当前这个值的种类数，那么转移方程为dp[now][j] = dp[pre][j] + dp[pre][j^a[i]]。因为a^b=c的话，c^b=a，所以j^a[i]就可以得到通过异或a[i]转移到j的那个状态了。然后可以用滚动数组压缩一下。
代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 typedef long long ll; 6 7 const int lim = 1<<20; 8 9 int n,k;10 int a[50];11 ll dp[2][lim];12 13 int main()14 {15 int T;scanf("%d",&T);16 for(int kase=1;kase<=T;kase++)17 {18 scanf("%d%d",&n,&k);19 for(int i=1;i<=n;i++) scanf("%d",a+i);20 21 memset(dp,0,sizeof(dp));22 dp[0][0] = 1;23 int now = 0;24 for(int i=1;i<=n;i++)25 {26 now = 1 - now;27 for(int j=0;j<lim;j++)28 {29 dp[now][j] = dp[1-now][j] + dp[1-now][j^a[i]];30 }31 }32 ll ans = 0;33 for(int i=k;i<lim;i++) ans += dp[now][i];34 printf("Case #%d: %I64d\n",kase,ans);35 }36 }
HDU 5119 Happy Matt Friends ——（背包DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。