1. 只能说大盗是福尔摩斯
2. 唯一的正解就是趁着月黑风高站在商铺门口
3. 我又不是警报器
4. 只要洗劫不相邻的商铺就不会惊动警察
5. 我相信警察局是不是相邻的（你知道我想干什么）
6. 对于第一组样例，阿福选择第2家警察局行窃，才获得的8人民币，可见他多么慷慨

#include<bits/stdc++.h>
using namespace std;
long long n,t,a[1000005],dp[1000005];
int main(){
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n;
		memset(dp,0,sizeof(dp));
		for(int j=1;j<=n;j++){
			cin>>a[j];
		}
		dp[1]=a[1];
		for(int j=2;j<=n;++j){
			dp[j]=max(dp[j-1],dp[j-2]+a[j]);
		}
		cout<<dp[n]<<endl;
	}
	return 0;
}

这题解呢啊，本来是要前几个星期前就写的，但是因为某些原因，推迟了。

好，接下来进入正题

这题的确啊，就是DP

定义$dp[i]$表示阿福打劫到第$i$个店时的最大金额

好，我们直接看状转：$dp[i]=max(dp[i-1],dp[i-2]+a[i]);$

因为必须要至少隔开一个店铺所以呢状转就得写成这样。

好，最后再来设置一下边界 $dp[1]=a[1];$就完成了

附上$ACCODE$

#include<bits/stdc++.h>
using namespace std;
long long dp[100005];
int main()
{
	long long t,n;
	cin>>t;
	for(long long p=0;p<t;p++)
	{
		memset(dp,0,sizeof(dp));
		cin>>n;
		long long a[n+1];
		long long o; 
		for(long long i=1;i<=n;i++)
		{
			cin>>a[i]; 
		} 
		dp[1]=a[1];
		for(long long i=2;i<=n;i++)
		{
			dp[i]=max(dp[i-1],dp[i-2]+a[i]);
		}
		cout<<dp[n]<<endl;
	}
}

$\LaTeX$666

/************************************
Note Book:
************************************/
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <math.h>
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int t , n , maxx;
int  a[N];
int dp[N];
int main()
{
	cin >> t;
	while( t-- )
	{
		cin >> n;
		for(int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		memset(dp , 0 , sizeof dp);
		dp[1] = a[1];
		for(int i = 2; i <= n; i++)
		{
			dp[i] = max(dp[i - 1] , dp[i - 2] + a[i]);
		}
		cout << dp[n] << endl;
	}
	return 0;
}

#include<iostream>
#include<string>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
using namespace std;
#define LL long long
const int N = 1e6+10;
const int INF = 0x3f3f3f3f;
int n,a[N],dp[N],dp2[N]; 
int main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	int T;
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++){
			dp[i]=dp2[i-1]+a[i];
			dp2[i]=max(dp[i-1],dp2[i-1]);
		}
		cout<<max(dp[n],dp2[n])<<endl;
	}
	
	return 0;
}

这道题一看就是DP

第一眼看上去挺简单的，知识一个简简单单，我迅速推出了状态转移方程: dp[i]=max(dp[i],dp[j]+a[i]),然后写了段代码:

#include<bits/stdc++.h>
using namespace std;
long long dp[100001],a[100001];
int main()
{
	long long t,n;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		memset(dp,0,sizeof(dp));
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		dp[1]=a[1];
		for(int i=2;i<=n;i++)
		{
			dp[i]=a[i];
			for(int j=1;j<i-1;j++)
			{
				dp[i]=max(dp[i],dp[j]+a[i]);
			}
			dp[i]=max(dp[i],dp[i-1]);
		}
		cout<<dp[n]<<endl;
	}
}

当然，请不要CTJ,而且如果你也像这样写了，~那么恭喜你收获满屏的TLE~ 那么现在我们进行一下优化，我们要把dp的循环从二维压缩到一维，那么我们可以把dp数组改成一个二维数组dp[100001][2]分别表示两个状态选和不选，其中不选的数组中的值可以通过上一个不选的变量和上一个选的变量求出，也就是dp[i][0]=max(dp[i-1][0],dp[i-1][1]); 而选的那个数组中的值因为不能连续选，所以只能从上一个选的变量求得，也就是dp[i][1]=dp[i-1][0]+a[i]。 以上两条式子就是状态转移方程了，也就是: dp[i][0]=max(dp[i-1][0],dp[i-1][1]); dp[i][1]=dp[i-1][0]+a[i]; 有了正确的思路和正确的状态转移方程，我们就可以写出一下代码:

#include<bits/stdc++.h>
using namespace std;
long long dp[100001][2],a[100001];
int main()
{
	long long t,n;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		memset(dp,0,sizeof(dp));//memset是按字节赋值的，所以只有第二个参数为0或-1的情况下不会赋值错误
//这里的memset其实没有必要写,你想写也不出问题，但是第二个参数只能填0
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		dp[1][1]=a[1];//设定边界
		for(int i=2;i<=n;i++)//如果i从一开始就不需要设定上面的边界，反正没有意义
		{
			dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
			dp[i][1]=dp[i-1][0]+a[i];
//通过状态转移方程求出dp数组的值
		}
		cout<<max(dp[n][1],dp[n][0])<<endl;//最后的答案不一定是选的那边的答案,所以选和不选两个数组中的最大值才是答案
	}
}

如果你跟着我一步步写出了这段代码并且没有错误，那么恭喜你，收获一片AC！

#include<iostream> using namespace std; int t,n,a[100001],dp[100001],ans; int main(){ cin>>t; while(t--){ cin>>n; ans=0; for(int i=1;i<=n;i++){ cin>>a[i]; dp[i]=a[i]; } for(int i=2;i<=n;i++){ dp[i]=max(dp[i-1],dp[i-2]+dp[i]); } cout<<dp[n]<<endl; } return 0; } ```

#include<iostream> using namespace std; int t,n,a[100001],dp[100001],ans; int main(){ cin>>t; while(t--){ cin>>n; ans=0; for(int i=1;i<=n;i++){ cin>>a[i]; dp[i]=a[i]; } for(int i=2;i<=n;i++){ dp[i]=max(dp[i-1],dp[i-2]+dp[i]); } cout<<dp[n]<<endl; } return 0; }