【实验基地】

【题目描述】

给定一个2×N的矩形,每个格子有一个价值,请你从中选出一块子矩形,并且在子矩形的第一层挖掉一块,使其变成一个凹字形,使得这个凹字形的和最大。(只能是凹字形!像矩形或者L形之类的就不用来了)

比如

3     4     -2     5    -4     -5     10     12     -8

10   -1    -5     8     7     -3      0      2        9

红色就是一块合法的凹字形矩阵(但可能不是最优的)

【输入格式】

第一行有一个整数N,表示登陆地带的大小是2×N

随后的两行每一行有N个整数(其绝对值均不超过10^6),表示对应的矩形格子的价值,各个整数之间用一个空格隔开。

【输出格式】

只有一行输出,为整数M,即所确定的子矩形的最大价值。

【输入样例】

4

-1 2 -3 4

5 6  7 8

【输出样例】

31

【样例解释】

-1    2     -3     4

5     6      7      8

【数据规模】

对于100%的数据3<n≤500000.

大DP,考虑dp第二维为1表示矩形最优解,2表示L形最优解,3表示凹形最优解。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*