首页 > 其他 > 详细

UVA 11205 The broken pedometer(子集枚举)

时间:2014-06-18 12:31:29      阅读:401      评论:0      收藏:0      [点我收藏+]

B - The broken pedometer
Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu
Appoint description: 

Description

bubuko.com,布布扣
 The Broken Pedometer 

The Problem

A marathon runner uses a pedometer with which he is having problems. In the pedometer the symbols are represented by seven segments (or LEDs):

bubuko.com,布布扣

But the pedometer does not work properly (possibly the sweat affected the batteries) and only some of the LEDs are active. The runner wants to know if all the possible symbols:

bubuko.com,布布扣

can be correctly identified. For example, when the active LEDs are:

bubuko.com,布布扣

numbers 2 and 3 are seen as:

bubuko.com,布布扣

so they cannot be distinguished. But when the active LEDs are:

bubuko.com,布布扣

the numbers are seen as:

bubuko.com,布布扣

and all of them have a different representation.

Because the runner teaches algorithms at University, and he has some hours to think while he is running, he has thought up a programming problem which generalizes the problem of his sweat pedometer. The problem consists of obtaining the minimum number of active LEDs necessary to identify each one of the symbols, given a number P of LEDs, and N symbols to be represented with these LEDs (along with the codification of each symbol).

For example, in the previous sample P = 7 and N = 10. Supposing the LEDs are numbered as:

bubuko.com,布布扣

The codification of the symbols is: "0" = 1 1 1 0 1 1 1; "1" = 0 0 1 0 0 1 0; "2" = 1 0 1 1 1 0 1; "3" = 1 0 1 1 0 1 1; "4" = 0 1 1 1 0 1 0; "5" = 1 1 0 1 0 1 1; "6" = 1 1 0 1 1 1 1; "7" = 1 0 1 0 0 1 1; "8" = 1 1 1 1 1 1 1; "9" = 1 1 1 1 0 1 1. In this case, LEDs 5 and 6 can be suppressed without losing information, so the solution is 5.

The Input

The input file consists of a first line with the number of problems to solve. Each problem consists of a first line with the number of LEDs (P), a second line with the number of symbols (N), and N lines each one with the codification of a symbol. For each symbol, the codification is a succession of 0s and 1s, with a space between them. A 1 means the corresponding LED is part of the codification of the symbol. The maximum value of P is 15 and the maximum value of N is 100. All the symbols have different codifications.

The Output

The output will consist of a line for each problem, with the minimum number of active LEDs necessary to identify all the given symbols.

Sample Input

2
7
10
1 1 1 0 1 1 1
0 0 1 0 0 1 0
1 0 1 1 1 0 1
1 0 1 1 0 1 1
0 1 1 1 0 1 0
1 1 0 1 0 1 1
1 1 0 1 1 1 1
1 0 1 0 0 1 0
1 1 1 1 1 1 1
1 1 1 1 0 1 1
6
10
0 1 1 1 0 0
1 0 0 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
1 1 0 1 0 0
1 0 0 1 0 0
1 1 1 0 0 0
1 1 1 1 0 0
1 0 1 1 0 0
0 1 1 0 0 0

Sample Output

5
4




题意大概是问你最少要多少根二极管就能把所有的排列区分出来。。。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
int mat[105][20];
int main()
{
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    int p,n;
    while(T--)
    {
        scanf("%d%d",&p,&n);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=p;j++)
        scanf("%d",&mat[i-1][j-1]);
        int ans=500;
        int choose[20];
        for(int i=1;i<(1<<p);i++)
        {
            bool flag=true;
            memset(choose,0,sizeof(choose));
            int k=0;
            for(k=0;(1<<k)<=i;k++)
                if((1<<k)&i)choose[k]=1;
            for(int i_=0;flag&&i_<n;i_++)
            for(int j=i_+1;flag&&j<n;j++){
                bool t=true;///相同的
                for(int l=0;t&&l<k;l++)if(choose[l])
                {
                    if(mat[i_][l]!=mat[j][l])t=false;///没有相同的
                }
                if(t)flag=false;///有相同的失败
            }
            if(flag){
                int temp=0;
                for(int c=0;c<k;c++)if(choose[c])temp++;
                ans=min(ans,temp);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}



UVA 11205 The broken pedometer(子集枚举),布布扣,bubuko.com

UVA 11205 The broken pedometer(子集枚举)

原文:http://blog.csdn.net/acvcla/article/details/31407049

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!