三消游戏
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 31 Accepted Submission(s) : 11
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
程序设计大赛这样的活动，报名选手自然少不了当当姐啦。作为太吾村里最聪明的同学，她不一会儿便完成了比赛中的所有题目。酷爱三消游戏的她顺手在草稿纸上发明了一种简单的数字三消游戏。
游戏中，每回合会给出一行n个数字，我们设其中第i个数字为a[i]。当当姐会把数字a[i]想象为一堆位于第i列的，高度为a[i]的积木（a[i]可以为0），而她每次操作，可以选择下标连续（如3,4,5）的三个非空积木堆，在每个积木堆上都各拿走一块积木。而如果再也找不到下标连续的三个非空积木堆，游戏便结束了。
当当姐想要知道的是，最少操作多少次，以及最多操作多少次，可以使得游戏结束呢？
注意，当一堆积木被消除为空时，所有积木的编号并不会发生改变。
游戏中，每回合会给出一行n个数字，我们设其中第i个数字为a[i]。当当姐会把数字a[i]想象为一堆位于第i列的，高度为a[i]的积木（a[i]可以为0），而她每次操作，可以选择下标连续（如3,4,5）的三个非空积木堆，在每个积木堆上都各拿走一块积木。而如果再也找不到下标连续的三个非空积木堆，游戏便结束了。
当当姐想要知道的是，最少操作多少次，以及最多操作多少次，可以使得游戏结束呢？
注意，当一堆积木被消除为空时，所有积木的编号并不会发生改变。
Input
第一行为一个整数T，代表数据组数。
接下来，对于每组数据――
第一行两个整数n，表示积木的堆数。
第二行有n个用空格隔开的整数，其中第i个数字a[i]代表第i列的积木个数。
数据保证――
1 <= T <= 1000
0 <= a[i] <= 500
设a[1] + a[2] + ... + a[n] = m，有:
对于98%的数据，3 <= n <= 10 && 0 <= m <= 100
对于100%的数据，3 <= n <= 100 && 0 <= m <= 1000
接下来，对于每组数据――
第一行两个整数n，表示积木的堆数。
第二行有n个用空格隔开的整数，其中第i个数字a[i]代表第i列的积木个数。
数据保证――
1 <= T <= 1000
0 <= a[i] <= 500
设a[1] + a[2] + ... + a[n] = m，有:
对于98%的数据，3 <= n <= 10 && 0 <= m <= 100
对于100%的数据，3 <= n <= 100 && 0 <= m <= 1000
Output
对于每组数据，输出两个数字。
该行有2个整数，分别表示当当姐游戏结束前最少的操作数和最多的操作数。
该行有2个整数，分别表示当当姐游戏结束前最少的操作数和最多的操作数。
Sample Input
4 3 4 6 8 5 0 0 10 0 0 6 2 3 4 5 6 7 7 8 3 2 6 2 5 8
Sample Output
4 4 0 0 5 7 2 4
Source
642超哥