Блог пользователя UCI-Night

Автор UCI-Night, 12 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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;
}