UCI-Night's blog

Help
By UCI-Night, 12 years ago, In English

Given n bitmasks of size 8, count the subsets with the bitwise OR equal to 11111111. How solve this?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Using DP try to understand this code.

#include<cstdio>
#define MAX (1<<8)
int n;
int N[100];
int D[100][(1<<8)];

int main(){
  scanf("%d",&n);
  for(int i = 0 ; i < n ; i++)
  	scanf("%d",N+i);
  	
  D[0][0] = 1;
  for(int i = 0 ; i < n ; i++)
  {
      for(int j = MAX - 1 ; j >= 0 ; j--)
	  {
	     if(i)D[i][j]+=D[i-1][j];
		 D[i][ j | N[i] ]+=D[i][j];
	  }		
  }
  printf("%d\n",D[n-1][(1<<8) - 1]);
	return 0;
}
→ Reply