本文主要是介绍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;
}
这篇关于HDU 4901 DP背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
