题解

题目描述

工厂被划分为 $m$ 个片区，工厂内安装了 $n$ 个摄像头。每个摄像头监控哪些片区由一个长度为 $m$ 的二进制字符串描述，字符串中第 $i$ 位为 $'1'$ 表示该摄像头能监控第 $i$ 个片区，否则不能监控。由于监控室大屏幕一次最多只能展示 $8$ 个摄像头画面，所以需要从摄像头中选取一个子集（至少一个、至多 $8$ 个），使得这些摄像头合起来监控的片区数量最多。若多个选法能达到最大监控片区数量，则统计方案数（注意：同一片区被多个摄像头监控只计一次）。

解题思路

题目内容

小歪的工厂一共分为 $m$ 个片区，他一共为工厂安装了 $n$ 个监控摄像头，每一个监控摄像头能够监控的片区使用一个长度为 $m$ ，仅由字符 $'0'$ 和 $'1'$ 组成的字符串表示，其中，第 $i$ 个为表示监控摄像头能够监控第 $i$ 个片区，否则表示不能监控到。

监控室的大屏幕一次性至多只能同时展示八个监控提像头的画面，小歪想知道，怎样选取监控摄像头，能够使得监控的片区数量最多，以及一共有多少个不同的选取方案。注意，如果有两个监控摄像头监控到同一片片区，那么这片片区只计算一次。

输入描述

第一行输入两个正整数 $n,m(1≦n≦25;1≦m≦100)$ 代表临控摄像头数量、片区数量。

此后 $n$ 行，第 $i$ 行输入一个长度为 $m$ ，仅由字符 $'0'$ 和 $'1'$ 组成的字符串 $s_i$ ，表示第 $i$ 个监控摄像头能够监控的片区。

数据保证至少有一个摄像头能监控到至少一个片区。

输出描述

输出一行，两个整数，表示最多监控的片区数量，以及一共有多少个不同的选取方案。

样例1

输入

3 4
1111
0010
1101

输出

4 5

说明

在这个样例中，一共有七种选取方案：

• 单展示第一个摄像头，可以监控到四片片区；

• 单展示第二个提像头，可以监控到一片片区；

• 单展示第三个摄像头，可以监控到三片片区；

• 同时展示第一个和第二个摄像头，可以监控到四片片区；

• 同时展示第一个和第三个摄像头，可以监控到四片片区；

• 同时展示第二个和第三个摄像头，可以监控到四片片区;

• 同时展示第一个、第二个、第三个摄像头，可以监控到四片片区；

综上，最多监控到四片片区，一共有五种选取方案。