#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, a[55], f[305];
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    f[1] = a[1];
    f[2] = max(a[1], a[2]);
    for (int i = 3; i <= n; i++)
        f[i] = max(f[i - 1], f[i - 2] + a[i]);
    cout << f[n] << endl;
    return 0;
}

本题是一个经典的动态规划题目。 - 首先设计状态：设dp[i]表示前i个不连续的数的最大和 - 设计完成之后，我们只需要求dp[1~n]中的最大值即可 - 状态转移： https://img-blog.csdnimg.cn/dda7269a3d1f4cdda59528513dd4a480.png#pic_center

不难发现： ① dp[1] = a[1]，即前1个不连续的数的最大和就是它本身 ② dp[2] = max(a[1]，a[2])，即前2个不连续的数的最大和就是前两个数中较大的那个数 ③ 对于dp[k]，即前k个不连续的数的最大和，此时要分两种情况(一种是选第k个数，另一种情况是不选第k个数) https://img-blog.csdnimg.cn/44512d8e5e3f413a92c87f3325d861bd.png#pic_center 根据以上分析，得出本题的状态转移方程：

dp[i] = max(dp[i - 2] + a[i]，dp[i - 1])

上代码：

    scanf("%d",&n);
    for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
    
    dp[1] = a[1];
    dp[2] = max(a[1],a[2]);
    
    maxn = max(dp[1],dp[2]);//与dp[1],dp[2]比较,更新maxn
    
    for (int i = 3;i <= n;i++) 
    {
        dp[i] = max(dp[i - 1],dp[i - 2] + a[i]);
        maxn = max(maxn,dp[i]);//与dp[1~n]比较,更新maxn
    }
    //for (int i = 1;i <= n;i++) printf("%d ",dp[i]);
    cout << maxn << endl;//maxn = dp[n]

至此。我们就完美解决啦~

欢迎各位有意的小伙伴致信ylkj_email@163.com,一同组建编程工作室。

对于每一个数字，有取和不取两种决策。
设f[i]为到a[i]为止的和
取a[i],f[i]=f[i-2]+a[i]因为不能相邻，所以转移到i-2
不取a[i],f[i]=f[i-1]
#include<bits/stdc++.h>
using namespace std;
long long n,a[55],f[55],ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	f[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		f[i]=max(f[i-1],f[i-2]+a[i]);
		ans=max(ans,f[i]);
	}
	cout<<ans;
	return 0;
}

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。

严禁抄题解，发现后取消成绩