【DP】【构造】NOIp模拟题 演讲 题解

    极其考思维的好题

 

题目背景

众所周知,$\mathrm{Zdrcl}$是一名天天$\mathrm{AK}$的高水平选手。

作为一民长者,为了向大家讲述自己$\mathrm{AK}$的经验,他决定在一个礼堂里为大家举办一场演讲。

题目描述

这个礼堂拥有$N\times M$个位子,排成$N$行$M$列。每个位子都有一盏灯,一开始有的灯是亮的,有的灯是灭的。这个礼堂十分诡异,人们操作一次只能使某一行或某一列(某一行或某一列由操作者你自己来决定)的灯的明暗状态全都发生转变(显然,我们不一定可以把所有的灯都点亮)。

 

来听演讲的人只会坐在灯已经被点亮的位置, 所以可以听演讲的位置只会是一个只由灯是亮的的位子所组成的矩形(不然坐太乱,$\mathrm{Zdrcl}$会不高兴的) 。

 

$\mathrm{Zdrcl}$知道会有很多人来听演讲, 所以他希望找到一个经过若干操作后的面积最大的只由灯是亮的的位子所组成的矩形。 这个任务当然由想$\mathrm{AK}$的你来完成啦!

 

输入输出格式

输入格式:

第一行两个正整数表示$N,M$。

 

接下来有$N$行,每行有$M$个字符(‘#’表示这个灯初始状态是亮的,‘.’表示这个灯初始状态是暗的)。

 

输出格式:

一行一个整数表示你找到的矩形的面积。

 

输入输出样例

输入样例#1:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpdswj.html