存在於數組子集中的值的異或

Question

給定一個大小爲n的數組，其中只包含正整數。令l爲數組A中的最大數。生成數組B的大小爲0至l，使得B [j]是數組A的最大子集的大小，其XOR值等於j。

限制條件： 陣列的尺寸A可以是從在數組A爲1〜10000 元素的範圍可以從1到1000

例如：如果陣列A具有（1,2,3,4 ），那麼數組B將如下生成。

B（0）= 3作爲具有異或值0是（1,2,3）最大的子集，並且具有尺寸3.

B（1）= 2作爲具有異或值最大的子集1是（2,3），並且具有大小2

B（2）= 2作爲具有異或值2是（1,3）最大的子集，並且具有大小2

B（3）= 2作爲具有XOR值3的最大子集是（1,2）並且具有大小2.

B（4）= 4，作爲具有XOR值4的最大子集是（1,2,3,4）並且具有大小4 。

我的蠻力方法：生成數組A的所有非空子集，並計算每個子集的XOR，並在B [j]中保存具有XOR值j的最大大小子集。

有沒有更高效的方法來做到這一點？

Answer 1

我相信這會工作，我已經添加了註釋的幫助

#include <iostream> 
using namespace std; 
#define max(a, b) (a>b?a:b) 
int dp[10005][1001]= {0}; 
int main() { 
    // your code goes here 
    int n, a[10005]={0}, m, i,j, ans[1005]={0}; 
    // n denotes number of elements in array, m denotes the range(0, m) where you want to loop 
    scanf("%d%d",&n,&m); 
    for(i=1; i<=n; i++){ 
     // taking input 
     scanf("%d",&a[i]); 
    } 
    for(i=0;i<=10000;i++){ 
     for(j=0;j<=1000;j++){ 
      dp[i][j] = -1; 
     } 
    } 
    dp[0][0] = 0; 
    // dp[i][j] denotes what's the max num of elements whose xor = j using the first i elements 
    for(i=1; i<=n; i++){ 
     for(j=0; j<=1000; j++){ 
      if(dp[i-1][j] != -1){ 
       // if j was possible using i-1 elements the using a[i] (a[i]^j) can be made using i elements 
       dp[i][j^a[i]] = max(dp[i][j^a[i]], dp[i-1][j]+1); 
      } 
      dp[i][j] = max(dp[i][j], dp[i-1][j]); 
      if(dp[i][j] != -1){ 
       ans[j] = max(ans[j], dp[i][j]); 
      } 
     } 
    } 
    for(i=0;i<=m;i++){ 
     printf("%d\n", ans[i]); 
    } 
    return 0; 
} 

檢查在http://ideone.com/QuICHN