首页 > 代码库 > HDU4901 The Romantic Hero DP

HDU4901 The Romantic Hero DP

2024-07-15 03:09:11   225人阅读

 题意：给你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 }
View Code

 


联系
我们