#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int f[100009],a[100001];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            f[i]=a[i];
        }
        for(int i=2;i<=n;i++)
        {
            f[i]=max(f[i-2]+a[i],f[i-1]);
        }
        printf("%d\n",f[n]);
    }
    return 0;
}

《五个月前》

A1301 大盗阿福

题意

对于a集合（数组），构建子集b，使得b中元素在a中不相邻且总和最大。

题解

楼下2维太麻烦了

dp数组含义

规定dp[i]是指第a[0]到a[i]里的最大价值。

边界条件

显然，当i=1时，dp[i]就是取a[1]。 所以，边界条件就是dp[1]=a[1]。

状态转移方程

当我们去a[i]抢劫，则获得价值是之前抢的dp[i-2]（因为不能连着抢同一家店）和a[i]的总和。 当我们不去a[i]抢劫，则获得dp[i-1]的财产。 最后，取二者最大值。 即dp[i]=max(dp[i-1],dp[i-2]+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 j=1;j<=t;j++){
		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]=max(dp[i-1],dp[i-2]+a[i]);//状态转移方程
		cout<<dp[n]<<endl;//答案
    }
    return 0;
}

点赞！！！

`

#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;//最后的答案不一定是选的那边的答案,所以选和不选两个数组中的最大值才是答案
	}
}

#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;//最后的答案不一定是选的那边的答案,所以选和不选两个数组中的最大值才是答案 } }