超人衣服

【问题描述】

莫队长想要做一件超人衣服,大家都知道超人衣服中有一个很大的黄色S,其余的部分都是红色的。现在这个衣服还没染色,但有些地方已经被溅到了红色染料。所以莫队长想要你在其余的空白地方找到一个面积最大的S。
整件衣服被划分为n*m个小块,一个S被定义为5笔,每一笔的长度和宽度都是不确定的正整数。如下图的A是一个合法的S,B不是一个合法的S。

A B

【输入格式】

第一行两个数n,m。
接下来n行,每行m个数,第i行第j个数如果是0,表示这一块是空白,如果是1,表示这一块是红色。

【输出格式】

仅一个数,表示最大S的面积。

【数据范围】

对于20%的数据,5≤n,m≤10
对于100%的数据,5≤n,m≤100

【题解】

这道题听说是【NOI2013书法家】改过来的

这道题相对简单(不过一开始我不会做)

可以讲一个“S”横向切割分成五个部分:上面的横,左面的竖,中间的横,右面的竖,下面的横

那么就可以进行DP:dp[i][l][r][k]表示第i行l~r为第k个部分时的最优值

打代码也是打得很爽呢233

说点什么

您将是第一位评论人!

提醒
wpDiscuz