P3819.第2题-神奇的字符串
题目内容
TK 得到了一个神奇的字符串 s (下标从 1 开始)，该字符串长度为 n，仅由 {′0’,′1’} 构成，并且对于任意的下标 i ,若 i mod 2=1 ，则 si=′1’，否则 si=′0’ 。
此外，给定一个长度为 n−1 的整数数组 {a1,a2,…,an−1}。你可以重复进行如下操作，直到无法继续；
- 选择一个下标 i(1≦i<len(s))，且满足 si=si+1 ; 获得积分 ai ;删除 si 与 si+1，其余字符按原顺序拼接成新串。
注意，数组 a 在整个过程中不发生变化：每次选择的位置 i 始终对应同一个 ai ; 数组的长度与元素值均保持不变。
请分别求出完成全部操作后，累计积分的最大值与最小值。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦104) 代表数据组数，每组测试数据描述如下：
-
第一行输入一个整数 n(2≦n≦2×105) 表示字符串长度;
-
第二行输入 n−1 个整数 a1,a2,...,an−1(1≦ai≦109) 表示奖励积分数组。
除此之外，保证单个测试文件的 n 之和不超过 2×105 。
输出描述
对于每一组测试数据，新起一行，输出两个整数：
第一个整数表示累计积分的最大值，第二个整数表示累计积分的最小值。
样例1
输入
2
4
5 1 4
3
7 2
输出
10 6
7 2
说明
对于第一组测试数据原字符串 1010 最小值操作方式：
-
选择 s2,s3 得到 1 积分，字符串变为 10
-
选择 s1,s2 得到 5 积分，字符串变为空无法操作结束。
总共获得 6 积分，可以证明不存在比此积分更小的操作方式。
