题意:计数器有问题,现在给出p和n,p表示用p位二进制数来表示一个数,n表示有n个数分别用二进制给出。问最少用多少列就能把这n个数区别开。列数不一定连续。
思路:原来以为是用连续的m列来表示,WA了几次。这里用到了排列,用B[]来表示p位的排列,1表示取这一列,0反之。然后判断取这排列n个数是否相同。
刘汝佳 的算法竞赛入门经典 121页
#include <stdio.h> #include <string.h> int mat[105][20],B[20]; int min,p,n; void solve() { for (int i = 0; i < n-1; i ++) for (int j = i+1; j < n; j ++) { bool flag = false; for (int k = 0; k < p; k ++) if (B[k]&&mat[i][k]!=mat[j][k]) flag = true; if (!flag) return ; } int res = 0; for (int i = 0; i < p; i ++) if (B[i]) res ++; min = min > res ? res:min; } void subset(int cur) { if (cur == p) { solve(); return ; } B[cur] = 1; subset(cur+1); B[cur] = 0; subset(cur+1); } int main () { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int T; int i,j; while (~scanf ("%d",&T)) { while (T --) { scanf ("%d %d",&p,&n); for (i = 0; i < n; i ++) for (j = 0; j < p; j ++) scanf ("%d",&mat[i][j]); min = p; memset (B,0,sizeof(B)); subset(0); printf ("%d\n",min); } } return 0; }