8462：大盗阿福——动态规划基础（第2.6节）

8462:大盗阿福

总时间限制: 1000ms 内存限制: 65536kB
描述
阿福是一名经验丰富的老贼. 今夜 BMP 阿福计划今晚抢劫街上的各店.

整条街道共有N家商店，在每一家店铺内部存有一定数额的现金。通过调查发现，在阿福实施抢劫时会选择连续经营的两间店铺进行抢劫，并且一旦触发报警系统会立即引发警员快速赶到现场。

作为个老油条级别的大盗型角色存在，在这种情况下阿福显然无法避免成为警方的猎物

输入的第一行为一个整数值 T （满足 T ≤ 50），表示共有 T 组测试用例。
对于每一组测试用例：

• 第一行是一个正整数 N （满足 1 ≤ N ≤ 1×1e5），表示共有 N 家店铺。
• 第二行包含 N 个用空格分隔的正整数（每个不超过 1,003），代表各店铺中的现金金额。
  输出：
  针对每一组测试用例，在不触发警察警报的情况下计算阿福能获取的最大金额。
  样例输入解释：
  2 组测试用例中：
• 第一组有3家店铺分别拥有8元、7元、6元
• 第二组有4家店铺分别拥有8元、7元、6元、9元
  样例输出解释：
• 第一组最优选择是取8元
• 第二组合并取8+9=17 元

分析：

http://www.cnblogs.com/zzyh/p/6683813.html

盗取第i个店铺时，其最优解等于前i-2个店铺的最优解加上当前