首页 > 代码库 > hdu 4901 The Romantic Hero (dp)
hdu 4901 The Romantic Hero (dp)
题目链接
题意：给一个数组a，从中选择一些元素，构成两个数组s， t，使s数组里的所有元素异或
等于 t数组里的所有元素 位于，求有多少种构成方式。要求s数组里 的所有的元素的下标
小于 t数组里的所有的元素的下标。
分析：比赛的时候，刚开始脑子很乱，后来想了一下思路也敲了，发现自己的程序结果不对
自己一点一点计算后发现自己的程序有一部分计算重复了，其实还是dp的思路不够清晰。
d[i][j]代表第i个数 新产生的结果为数字 j 的个数。
AC代码：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstdio> 6 #include <set> 7 #include <vector> 8 #include <algorithm> 9 #define LL long long10 const int maxn = 1000+50;11 const int mo = 1000000000+7;12 using namespace std;13 __int64 cnt;14 int n, a[maxn];15 __int64 d[maxn][maxn], dt[maxn][maxn], temp[maxn][maxn];16 17 int main()18 {19 int T, i, j, x;20 scanf("%d", &T);21 while(T--)22 {23 cnt = 0;24 memset(d, 0, sizeof(d));25 memset(dt, 0, sizeof(dt));26 memset(temp, 0, sizeof(temp));27 scanf("%d", &n);28 for(i = 0; i < n; i++)29 scanf("%d", &a[i]);30 for(i = 0; i < n; i++)31 {32 for(j = 0; j < 1025; j++)33 {34 if(i!=0 && temp[i-1][j]) //让之前存在的和a[i]异或会产生新的存放在d数组里35 {36 x = (a[i]^j); //x有可能会大于j，所以不能用d数组直接累加37 d[i][x] += temp[i-1][j];38 }39 d[i][j] %= mo; //随时取余很重要，不然会wa40 }41 d[i][a[i]] ++; //加上自身42 for(j = 0; j < 1025; j++)43 {44 if(i != 0)45 temp[i][j] += temp[i-1][j] + d[i][j]; //temp数组用来维护目前所有的46 else //结果，并且不可以用d直接加，否则会重复47 temp[i][j] = d[i][j];48 temp[i][j] %= mo;49 }50 }51 memset(temp, 0, sizeof(temp));52 for(i = n-1; i >= 0; i--)53 {54 for(j = 0; j < 1025; j++)55 {56 if(temp[i+1][j])57 {58 x = (a[i]&j);59 dt[i][x] += temp[i+1][j];60 }61 dt[i][j] %= mo;62 }63 dt[i][a[i]] ++;64 for(j = 0; j < 1025; j++)65 {66 temp[i][j] += temp[i+1][j] + dt[i][j];67 temp[i][j] %= mo;68 }69 }70 for(i = n-2; i >= 0; i--)71 for(j = 0; j < 1025; j++)72 {73 dt[i][j] += dt[i+1][j]; //这是防止重复的，让dt数组累加，d数组不累加。74 dt[i][j] %= mo;75 }76 77 for(i = 0; i < n-1; i++)78 for(j = 0; j < 1025; j++)79 {80 cnt += d[i][j]*dt[i+1][j]; //用前面的乘以后面的81 cnt %= mo;82 }83 cnt %= mo;84 printf("%I64d\n", cnt);85 }86 return 0;87 }
顺便贴一下自己在比赛中wa的代码，思路不清。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstdio> 6 #include <set> 7 #include <vector> 8 #include <algorithm> 9 #define LL long long10 const int maxn = 1000+50;11 const int mo = 1000000000+7;12 using namespace std;13 __int64 cnt, f[maxn];14 int n, a[maxn];15 __int64 d[maxn][maxn], dt[maxn][maxn];16 17 int main()18 {19 int T, i, j, tmp;20 scanf("%d", &T);21 while(T--)22 {23 cnt = 0;24 memset(d, 0, sizeof(d));25 memset(dt, 0, sizeof(dt));26 memset(a, 0, sizeof(a));27 memset(f, 0, sizeof(f));28 scanf("%d", &n);29 for(i = 0; i < n; i++)30 scanf("%d", &a[i]);31 d[0][a[0]] = 1;32 f[a[0]] = 1;33 for(i = 1; i < n; i++)34 {35 for(j = 0; j < 1025; j++)36 {37 if(f[j])38 {39 tmp = (a[i]^j);40 d[i][tmp] += f[j];41 }42 d[i][j] %= mo;43 }44 d[i][a[i]] ++;45 f[a[i]] ++;46 }47 48 memset(f, 0, sizeof(f));49 dt[n-1][a[n-1]] = 1;50 f[a[n-1]] = 1;51 for(i = n-2; i >= 0; i--)52 {53 for(j = 0; j < 1025; j++)54 {55 if(f[j])56 {57 tmp = (a[i]&j);58 dt[i][tmp] += f[j];59 }60 d[i][j] %= mo;61 }62 dt[i][a[i]] ++;63 f[a[i]] ++;64 }65 66 for(i = n-2; i >= 0; i--)67 for(j = 0; j < 1025; j++)68 {69 dt[i][j] += dt[i+1][j];70 dt[i][j] %= mo;71 }72 73 for(i = 0; i < n-1; i++)74 for(j = 0; j < 1025; j++)75 {76 cnt += d[i][j]*dt[i+1][j];77 cnt %= mo;78 }79 cnt %= mo;80 printf("%I64d\n", cnt);81 }82 return 0;83 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。