这道题一看就是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！