| 6741870 | Accepted | 60 | 1002 | 2016-08-04 14:25:22 |
题目大意如下：给定n个LED灯串，每个灯串由p个LED灯构成，并给出每个灯串当下的状态，需要让所有灯串中规定的某些灯灭掉，询问最少剩下几盏正常的灯可以让我们分辨出LED灯原先代表的数字。
思路如下：正难则反。既然不可能一个个判断灯串所代表的符号，那么就只需判断若灭掉一些灯之后，n个灯串中剩下的亮灯是否有两组相同，若有，则分辨不出。因为灭掉的灯的种类和数量不定。那么，问题就可以转化为，用子集生成算法枚举剩下的灯串或灭掉的灯串，再判断是否出现了非法灯串就行了。而这里我用的是增量法枚举剩下的亮灯。
代码如下：（2KB）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int a[20],p,n,ans;
bool pdt[110][20];
bool same(int x,int y,int cur)
{
for(int i=0;i<cur;i++)
if(pdt[x][a[i]]^pdt[y][a[i]])
return 0;
return 1;
}
bool jud(int cur)
{
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(same(i,j,cur))return 0;
return 1;
}
void sub(int cur)
{
if(jud(cur))
ans=min(ans,cur);
int s=cur?a[cur-1]+1:0;
for(int i=s;i<p;i++){
a[cur]=i;
sub(cur+1);
}
}
void Init()
{
ans=0x3f3f3f3f;
scanf("%d%d",&p,&n);
for(int i=0;i<n;i++)
for(int j=0;j<p;j++)
scanf("%d",&pdt[i][j]);
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
Init();
sub(0);
printf("%d\n",ans);
}
return 0;
}