专栏文章

B4135 题解

ggetchar_unlocked
B4135题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipwjb23
此快照首次捕获于
2025/12/03 19:06
3 个月前
此快照最后确认于
2025/12/03 19:06
3 个月前
查看原文
题目传送门

思路

考虑动态规划。
用 FiF_i 表示到第 ii 个数所能取到最大的和是多少。则可以初始化 F2=x1+x2F_2=x_1+x_2，即为前 22 个数最大的和。
从第 33 个数开始向后遍历，有取与不取 2 种情况。若取，则必须舍去 xi−2x_{i-2}，因为这样可能会取成相邻的 44 个数，则 Fi←Fi−3+xi−1+xiF_i\gets F_{i-3}+x_{i-1}+x_i。若不取，最大值就是 Fi−1F_{i-1}。综合取其最大值，即为 Fi←max⁡(Fi−1,Fi−3+xi−1+xi)F_i\gets\max(F_{i-1},F_{i-3}+x_{i-1}+x_i)。
答案为 FnF_n。
AC CODE
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...