题目描述：

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺，每家店中都有一些现金。
阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
输入格式：
输入的第一行是一个整数 T，表示一共有 T 组数据。
接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。
第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。
输出格式：
对于每组数据，输出一行。
该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
数据范围
1≤T≤50,
1≤N≤1e5
输入样例

2
3
1 8 2
4
10 7 6 14

输出样例

8
24

样例解释
对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。
对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。

思路：

  这道题可能是我除了背包问题外，写得最顺的dp了。阿福对于一个店铺有两种选择：1-盗窃，0-不盗窃，
那么我们的dp数组就这样定义了：dp[n][2]（对于dp[i][1]表示前i个店铺，并盗窃第i个店铺的最大收益）。
既然这样，对于dp[i][0] 和 dp[i][1]的最优解怎么求呢？
  让我们先来想一下对于dp[i][0]这个状态该怎么求出来，当第i个店铺不被盗窃的时
候，那我们就能盗窃第i-1个店铺，也可以不盗窃第i - 1个店铺，所以dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]),
那么为什么前面的第i-2，i-3，...1个店铺的状态不用考虑呢，因为dp[i-1][1]和dp[i-1][0]已经是前面状态的最优解了.
  对于dp[i][1]这个状态也是一样的思考方式，就能顺理成章地得出另一个状态转移方程：dp[i][1] = dp[i - 1][0] + w[i];
  最后让我们愉快地AC吧！

Code

#include
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair PII;

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
int n, m, w[N];
int dp[N][2];

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> w[i];
	dp[1][0] = 0; dp[1][1] = w[1];
	for(int i = 2; i <= N; i ++){
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
		dp[i][1] = dp[i - 1][0] + w[i];
	}
	cout << max(dp[n][1], dp[n][0]) << endl;
}
int main(void){
	ios::sync_with_stdio(false);
	cin.tie(0);
    int _; cin >> _;
    while(_--) solve();
	return 0;
}