P2228 [HNOI2001]洋洋吃蛋糕

    • 16通过
    • 58提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 各省省选 2001(或之前) 湖南 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    洋洋是有名的“小馋猫”。他爱吃许多东西,但也有一些不爱吃的东西。一天,洋洋发现家中有一块刚烤好的长方形的蛋糕,而且蛋糕里放上了各种各样的东西,有爱吃的草莓,奶酪,也有不爱吃的核桃仁。这使得洋洋有一些为难,到底是吃还是不吃呢?这时,爷爷看出了洋洋的烦恼,然后说:你若能够遵守以下几条规则的话,蛋糕可以随便吃:

    (1)蛋糕的尺寸为N×M,在吃之前,需先把蛋糕划分成N×M个单位蛋糕块,然后对每一个单位蛋糕块按照自己的喜好给其打分,分数越高表示越爱吃,反之则表示越不爱吃。这个分数为这一个单位蛋糕块的好吃程度值。

    (2)每一个单位蛋糕块要么全部被吃掉,要么不吃。

    (3)被吃掉的蛋糕块必须成长方形或正方形,是由一些单位蛋糕块组成的,且蛋糕块的两边必须和原来的大蛋糕块的两边平行。一块蛋糕块的好吃程度值就是所有组成这个蛋糕块的单位蛋糕块的分数之和。

    (4)被吃掉的蛋糕块的尺寸任意,且块数也任意。

    (5)为了保持蛋糕块的美观,所有被吃掉的蛋糕块在原来的大蛋糕块中的位置不能相邻,且不能重叠。如图1和图2的吃法是不允许的,而图3和图4的吃法是允许的。

    ![](https://cdn.luogu.org/upload/pic/1295.png) 

    (6)所有被吃掉的蛋糕块的好吃程度值之和最大。

    爷爷的话并没有消去洋洋的烦恼,因为他只能做好第1点,而不知如何选择蛋糕块。于是,洋洋请你帮忙选择蛋糕块,以使得所有被吃掉的蛋糕块的好吃程度值之和最大。

    输入输出格式

    输入格式:

    第一行是两个数N和M。1≤N≤200,1≤M≤10。

    以下N行是一个N行M列的矩阵,第i行第j列的数表示单位蛋糕块(i,j)的好吃程度值C(-100≤C≤100)。

    输出格式:

    只有一个数,即为最大的好吃程度值。

    输入输出样例

    输入样例#1: 复制
    2 3                            
    4 5 -2
    -1 2 1
    
    输出样例#1: 复制
    10
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。