UVa11205损坏的步数计

题意：有一组编码，用其中最少的位数来区分这些编码。

思路：相当于枚举一个集合的所有子集，然后选择符合要求的势最小的集合。

            子集生成有三种方法，但每一种子集的生成都没有明显的规律，至少不是从1个元素、2个元素到n个元素这样的顺序生成的，所以还是要枚举出所有的子集才行。这里用的增量构造法来枚举子集。

Code：

#include
void print_subset(int p,int n,int *A, int cur);
bool have_same(int cur,int n);
int codi[101][16];
int A[15+5];
int min;
int main()
{
//freopen("11205.in","r",stdin);
//freopen("11205.out","w",stdout); int t;
scanf("%d",&t);
while(t-->0)
{
min=20;
int p,n;
scanf("%d%d",&p,&n);
for(int i=0;i for(int j=0;j {
scanf("%d",&codi[i][j]);
}
print_subset(p,n,A,0);
printf("%d\n",min);
}
return 0;
}
void print_subset(int p,int n,int *A, int cur)
{
if(cur && have_same(cur,n)==false) min=cur int s=cur?A[cur-1]+1:0;
for(int i=s;i {
A[cur]=i;
print_subset(p,n,A,cur+1);
}
}
bool have_same(int cur,int n)
{
for(int i=0;i {
for(int j=i+1;j {
bool flag=true;//标记codi数组的第i行与第j行是否相同
for(int m=0;m {
if(codi[i][A[m]]!=codi[j][A[m]]) { flag=false; break;}
}
if(flag) return true;
}
}
return false;
}