#PQJ324x6150. QOJ 324_6150

    ID: 2914 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:AHOI 2014动态规划

QOJ 324_6150

2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题 安徽 合肥 2014.4.18 拼图 【故事背景】 JYY 最近迷上了拼图游戏。作为一个计算机科学家,JYY 有一套黑白色的 拼图,他希望通过合理的拼接,使得拼出的最终图案中,能包含面积最大的全白 色子矩形。 【问题描述】 JYY 一共有S 块拼图,并且由1 到S 编号。编号为i 的拼图是一个N 行 列 的方格矩形,每个方格都为黑色或者白色。 一开始JYY 将他的这S 块拼图按照编号顺序左右相连依次放在桌上拼成了 一个N 行M 列(这里

)的大矩形。 之后JYY 发现,可以通过改变这S 块拼图的连接次序,使得拼成的N 行M 列的大矩形中,最大全白子矩形面积变大。 现在JYY 想知道,怎么拼才能得到最大的全白子矩形呢?请你帮助他计算 出最佳的拼接方案。 【输入格式】 从文件puzzle.in 中读入数据。 每个输入文件中包含多组测试数据。输入文件第一行包含一个整数T,代表 测试数据的组数,接下来按顺序描述了每组测试数据。 每组测试数据的第一行包含两个整数S 和N。 接下来S 组输入,第i 组对应编号为i 的拼图。 在第i 组输入中,第一行包含一个整数 ; 接下来N 行描述一个N 行 列的0/1 矩形; 其中第x 行y 列为0 则表示该拼图对应位置的颜色是白色,反之则为黑色。 【输出格式】 输出到文件puzzle.out 中。 对于每组数据输出一行包含一个整数ans,表示最大可能的全白色子矩形的面 积。 【样例输入】 1 3 4 4 1001 0000

2014 年安徽省青少年信息学奥林匹克竞赛

中学组试题 安徽 合肥 2014.4.18 0010 1001 3 000 010 000 011 2 00 10 01 00 【样例输出】 6 【样例说明】 最佳方案所最终拼成的大矩形为 000100100 010000010 000001001 011100100 粗体部分是面积为6 的白色子矩形。 【数据规模与约定】 对于10%的数据满足 ; 对于30%的数据满足 ; 对于50%的数据满足 ; 对于100%的数据满足

    。