7873: BZOJ3873：[Ahoi2014]拼图
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
JYY最近迷上了拼图游戏。作为一个计算机科学家，JYY有一套黑白色的拼图，他希望通过合理的拼接，使得拼出的最终图案中，能包含面积最大的全白色子矩形。JYY一共有S块拼图，并且由1到S编号。编号为i的拼图是一个N行列的方格矩形，每个方格都为黑色或者白色。一开始JYY将他的这S块拼图按照编号顺序左右相连依次放在桌上拼成了一个N行M列（这里M=Sigma(Wi)(1<=i<=S）的大矩形。之后JYY发现，可以通过改变这S块拼图的连接次序，使得拼成的N行M列的大矩形中，最大全白子矩形面积变大。现在JYY想知道，怎么拼才能得到最大的全白子矩形呢？请你帮助他计算出最佳的拼接方案。
输入格式
每个输入文件中包含多组测试数据。输入文件第一行包含一个整数T，代表
测试数据的组数，接下来按顺序描述了每组测试数据。 每组测试数据的第一行包含两个整数S和N。 接下来S组输入，第i组对应编号为i的拼图。 在第i组输入中，第一行包含一个整数； 接下来N行描述一个N行列的0/1矩形； 其中第x行y列为0则表示该拼图对应位置的颜色是白色，反之则为黑色。输出格式
对于每组数据输出一行包含一个整数ans，表示最大可能的全白色子矩形的面积。
样例输入
1 34 4 1001 0000 0010 1001 3 000 010 000 011 2 00 10 01 00
样例输出
6
提示
对于100%的数据满足1<=S,N,Wi<=10^5,N*Sigma(Wi)<=10^5,T<=3 添加数组一组--2015.02.28
题目来源
By 佚名上传