首页 > 代码库 > HDU4901 The Romantic Hero DP
HDU4901 The Romantic Hero DP
题意:给你n个数,问你将数分成两个数组,S,T ,T 中所有元素的需要都比S任意一个大,问你S中所有元素进行 XOR 操作和 T 中所有元素进行 &操作值相等的情况有多少种。
解题思路:两个二维DP,等于背包问题,dpy[i][j] 代表选 数组 S 前 i 个数 状态为 j 的 情况有多少种。(这个是从前往后dp的)
然后我们还需要知道 dpx[i][j] ,代表选 T 数组 i-n个数的时候状态为 j 的情况数, (从后往前dp)
答案就是中间过程中 dpx[i]][j], i 必选的那种情况,把这种情况和前面 dpy 对应情况相乘累加就行。
解题代码:
1 // File Name: 1005.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月31日 星期四 15时38分31秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long 25 using namespace std;26 #define M 100000000727 LL dpy[1002][2155];28 LL dpx[1002][2155];29 int a[1002];30 31 int main(){32 int t; 33 scanf("%d",&t);34 while(t--)35 {36 int n; 37 scanf("%d",&n);38 memset(dpy,0,sizeof(dpy));39 memset(dpx,0,sizeof(dpx));40 int temp ; 41 for(int i = 1;i <= n;i ++)42 {43 scanf("%d",&a[i]);44 dpy[i][a[i]] = 1; 45 for(int j = 0;j <= 1050;j ++)46 { 47 if(dpy[i-1][j])48 {49 dpy[i][j] =(dpy[i][j]+dpy[i-1][j])%M;50 dpy[i][j^a[i]] = (dpy[i][j^a[i]]+dpy[i-1][j]) % M; 51 }52 }53 }54 LL ans = 0 ; 55 for(int i = n; i >= 2 ;i -- )56 {57 dpx[i][a[i]] = 1 ; 58 ans = (ans+dpy[i-1][a[i]])% M;59 int tsum[1058];60 memset(tsum,0,sizeof(tsum));61 for(int j = 0 ;j <= 1048;j ++)62 {63 if(dpx[i+1][j])64 {65 ans = (ans + dpy[i-1][j&a[i]]*dpx[i+1][j])%M;66 tsum[j&a[i]] = (tsum[j&a[i]] + dpx[i+1][j]) % M;67 }68 }69 for(int j = 0;j <= 1050 ;j ++)70 dpx[i][j] = (dpx[i+1][j] + dpx[i][j] + tsum[j])%M;71 }72 printf("%I64d\n",ans%M); 73 }74 return 0;75 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。