P1398 [NOI2013]书法家

    • 132通过
    • 305提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 枚举,暴力 骗分 NOI系列 2013 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小E同学非常喜欢书法,他听说NOI2013已经开始了,想题一幅“NOI”的字送给大家。

    小E有一张非常神奇的纸,纸可以用一个n 行m 列的二维方格矩阵来表示,为了描述方便,我们定义矩阵左下角方格坐标为(1,1) ,右上角方格坐标为(m,n) 。矩阵的每个方格有一个整数的幸运值。在格子上面写字可以增加大家的幸运度,幸运度的大小恰好是所有被笔写到的方格的幸运值之和。现在你要在上面写上 ‘N’,‘O’,‘I’三个字母。

    下面给出3个书法字的定义:

    1.‘N’由若干(≥3)个边平行于坐标轴的矩形组成,设有K个矩形组成(标号1~K),第i个矩形的左下角方格坐标设为(Li ,Bi) ,右上角坐标设为(Ri ,Ti) ,要求满足:

    a)Li<=Ri,Bi<=Ti

    b)对任意1<i<=K,有Li=R(i-1)+1

    c)对任意3<=i<K,有B(i-1)<=Ti<=T(i-1),Bi<=B(i-1);

    d)B2>B1,T2=T1,B(K-1)=B(K),T(k-1)<T(K)

    2.‘O’由一个大矩形A,挖去一个小矩形B得到,这两个矩形的边都平行于坐标轴。设大矩形左下角的方格坐标为(u,v),长为W宽为H,则小矩形B满足左下角方格坐标为(u+1,v+1) ,长W-2 ,宽H-2。要求满足:

    a)W>=3,H>=3

    b)u>R(K)+1

    3.‘I’为3个边平行于坐标轴的从下到上的实心矩形组成,从下到上依次标号为1,2,3,第i 个矩形的左下角格子坐标设为(Pi , Qi ),右上角格子坐标设为(Gi , Hi ),要求满足:

    a)Pi<=Gi,Qi<=Hi
    b)P1=P3>u+W,G1=G3
    c)Q1=H1=Q2-1,H2+1=Q3=H3
    d)P1<P2<=G2<G1

    下图是一个‘N’,‘O’,‘I’的例子

    另外,所有画的图形均不允许超过纸张的边界。现在小E想要知道,他能画出的最大幸运度是多少。

    输入输出格式

    输入格式:

    输入文件penman.in的第一行包含两个正整数n和m,分别表示矩阵的行数和列数。

    接下来n行,每行有m个整数,第i+1行的第j个数表示格子(j,n-i+1)的幸运值。

    输出格式:

    输出到文件penman.out中,输出一个整数T,表示小E能够获得的最大幸运度。

    输入输出样例

    输入样例#1: 复制
    3 13 
    1 1 -1 -1 1 -1 1 1 1 -1 1 1 1 
    1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 
    1 -1 -1 1 1 -1 1 1 1 -1 1 1 1 
    
    输出样例#1: 复制
    24
    输入样例#2: 复制
    3 13
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    
    
    输出样例#2: 复制
    -20

    说明

    样例1

    样例2

    数据范围

    对于所有的测试数据,保证n≥3,m≥12。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。