自动搬运

查看原文

来自洛谷，原作者为

	getchar_unlocked 互关条件见主页，关注我可以获得我小号 OIerDb 的关注（需私信） || 最后在线时间：2025年7月3日9时51分

搬运于2025-08-24 21:17:19，当前版本为作者最后更新于2025-03-16 13:16:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

考虑动态规划。

用 $F_i$ 表示到第 $i$ 个数所能取到最大的和是多少。则可以初始化 $F_2=x_1+x_2$，即为前 $2$ 个数最大的和。

从第 $3$ 个数开始向后遍历，有取与不取 2 种情况。若取，则必须舍去 $x_{i-2}$，因为这样可能会取成相邻的 $4$ 个数，则 $F_i\gets F_{i-3}+x_{i-1}+x_i$。若不取，最大值就是 $F_{i-1}$。综合取其最大值，即为 $F_i\gets\max(F_{i-1},F_{i-3}+x_{i-1}+x_i)$。

答案为 $F_n$。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e5+10;
int x[N],f[N];
signed main(){
	int n=read();
	for(int i=1;i<=n;++i)
		x[i]=read();
	f[2]=x[1]+x[2];
	for(int i=3;i<=n;++i)
		f[i]=max(f[i-1],f[i-3]+x[i-1]+x[i]);
	printf("%lld\n",f[n]);
	return 0;
}