OpenJudge

4074:积水量

总时间限制:
1000ms
内存限制:
65536kB
描述

凹凸不平的地面每当下雨的时候总会积水。假设地面是一维的,每一块宽度都为1,高度是非负整数,那么可以用一个数组来表达一块地面。例如[0,1,0,2,1,0,1,3,2,1,2,1]可以用来表示下图地面:


当下过雨后,地面就会积水,上图中蓝色的区域就是积水区域。现在给你一个数组表示地面,求下过雨后这块地面有多少积水量(假设不蒸发、不渗透)。

输入
第一行是一个整数m,表示有m组试样例,不超过100。
接下来m块,每块第一行是一个正整数n,表示地面总宽度(数组长度),不超过20000。
接下来一行是n个整数,用空格隔开,表示地面高度。
输出
对于每组输入,输出一个整数表示积水量。
样例输入
2
12
0 1 0 2 1 0 1 3 2 1 2 1
4
1 0 0 2
样例输出
6
2
全局题号
6711
添加于
2014-01-04
提交次数
1103
尝试人数
289
通过人数
216
您的评价 很水 简单 一般 较难 变态
  • 标签(多个标签用空格分隔):
  • 常用标签:
    递归   动态规划   贪心   搜索   枚举   模拟   数学   字符串处理   几何   高精度计算   图论  

共有14人评分

0.0%
0.0%
0.0%
21.4%
78.6%

已有的标签

数学(1) No(1) 无测试数据(1) 0.0000000000000(1) O(1)