B4135 题解

getchar_unlocked · 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;
}