【oiClass 2092】折型最大（DP）

89 阅读 0 评论 59 点赞

我是靠谱客的博主快乐寒风，最近开发中收集的这篇文章主要介绍【oiClass 2092】折型最大（DP），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

折型在日常生活中随处可见，比如闪电符号“ ” ，显示器的四个角等等；折型大致可以
分为四种类型（“┌”，“┐”，“└”，“┘”）。笨笨只对“┘”这种折型特别感兴趣（萝卜青菜，
各有所爱），笨笨想在一个二维矩阵中求“┘”这种数字加和最大的折型，具体规定如下描述：
对于一个 N 行*M 列的矩阵，一个折型区域必须满足：
1、它的形状为“┘”（不能是“└”，“┌”，或“┐”）；
2、它的宽度为 1；
3、它的横向长度和纵向长度都必须大于 1 且连续，不能等于 1（即不能退化为一条线或一
个点）；
现给出这个二维矩阵，求其中数字和最大的这种折型区域。

输入

第一行为 N,M，中间用一个空格隔开， N 表示矩阵的行数， M 表示矩阵的列数；
接下来是 N 行，每行 M 个整数，每 2 个整数之间用 1 个空格隔开，每个整数 A[i,j]在[-100,100]；

输出

一行一个整数，即满足题目要求的折型区域的最大数字和。

每一个点的纵横方向都做一遍最大连续区间和，那么一个点的最大折型就是左边的点与上面的点的最大连续区间和加上这个点的值。

 1 #include <cstdio>
 2 
 3 #define N 1001
 4 
 5 int n,m,a[N][N],s1[N][N],s2[N][N],ans=-0x7fffffff;
 6 #define max(x,y) (x>y?x:y)
 7 
 8 int main(void){
 9     scanf("%d%d",&n,&m);
10     for(int i=1;i<=n;++i)
11         for(int j=1;j<=m;++j)
12             scanf("%d",&a[i][j]);
13     for(int i=1;i<=n;++i)
14         for(int j=1;j<=m;++j)
15             s1[i][j]=max(s1[i][j-1],0)+a[i][j],
16             s2[i][j]=max(s2[i-1][j],0)+a[i][j];
17     for(int i=2;i<=n;++i)
18         for(int j=2;j<=m;++j)
19             ans=max(ans,a[i][j]+s1[i][j-1]+s2[i-1][j]);
20     printf("%d",ans);
21 }