uva 11205サブセット生成

テーマ:
デジタルチューブは7本のLEDランプで構成されており、ランプが壊れても何の数字なのか見分けられる場合があります.少なくとも数本のランプがあれば、すべての入力記号を見分けることができます.
抽象的に言えば、実際には0,1行列を与え、少なくともいくつかの列が必要で、すべての行を区別することができます.
この問題は最初はできないので、サブセットアルゴリズムを生成するのを見てやっと、幸いにも入力データは大きくなくて、さもなくばきっとタイムアウトしたでしょう、ACの過ぎた時間はすべて2000 msになりました.
私はビットベクトル法でサブセットを生成し、すなわち、iがサブセットAに存在するか否かを1つの配列B【i】=1で表し、iをサブセットAに加えるか否かを順次選択し、最後に得られたサブセット結果を出力する.この問題Nは100以下が要求されるため、2つの比較が可能であり、複雑度O(n 2)もそれほど大きくないが、あるサブセットの下にある各行の「値」(例えばP=10のサブセットは0,1,2,3,4であり、各行の0,1,2,3,4列の数にその列の重み値を乗じて一意の値を得た)を計算し、flag【】配列でこの「値」にアクセスしたかどうかを格納し、各行の「値」が異なることが十分条件であることを見分けることができます.

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int np,P,N,Minp;
int grid[105][16];

bool flag[65536];

void subset(int n,int B[],int cur)
{
	if (cur==n)
	{
		memset(flag,0,sizeof(flag));
		int count=0;
		for (int i=0;i<N;i++)
		{
			int dex=0;
			for (int k=0;k<cur;k++)
			{
				if (B[k])
				{
					if (i==0) count++;
					dex=dex+grid[i][k]*(int)pow(2,double(k));
				}
			}
			if (pow(2,(double)count)<P) 
				return;
			if (flag[dex]==0)
				flag[dex]=1;
			else return;
		}
		if (count<Minp) Minp=count;
		return;
	}
	B[cur]=1;
	subset(n,B,cur+1);
	B[cur]=0;
	subset(n,B,cur+1);
}

int main()
{
	cin>>np;
	while(np--)
	{
		cin>>P>>N;
		for (int i=0;i<N;i++)
		{
			for (int j=0;j<P;j++)
			{
				cin>>grid[i][j];
			}
		}
		Minp=P;
		int array[16];
		subset(P,array,0);
		cout<<Minp<<endl;
	}
	return 0;
}