题解：P14328 [JOI2022 预选赛 R2] 糖 2 / Candies 2

· · 题解

题目传送门

P14328 [JOI2022 预选赛 R2] 糖 2 / Candies 2

题意分析

从所有糖果中选择若干个，满足：

  1. 任意连续 K 个糖果中最多选两个。
  2. 美味度总和最大。

    分析

    本题考虑使用动态规划。

:::info[动态规划数组] 定义 f_{i,j} 表示最后两个糖果是 j 和 i 时获得的最大美味度。 :::

:::info[状态转移方程] 据题意，对于一个固定的 j 和当前 i，我们要找的就是 \max f_{i,j}(k \le \min(i-K,j-1))。

我们给每一个 j 一个前缀最大值数组。

最终答案就是 \max(\max a _ i,\max f_{i,j})。 :::

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[3005],f[3005][3005],qzh[3005][3005],ans; 
main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    long long c=0LL;
    for(int j=1;j<=n;j++)
    {
        for(int i=1;i<j;i++)
        {
            f[i][j]=a[i]+a[j];
            f[i][j]=max(qzh[max(min(i-1,j-k),c)][i]+a[j],f[i][j]);
            ans=max(ans,f[i][j]); 
            qzh[i][j]=max(qzh[i-1][j],f[i][j]);
        }
    } 
    cout<<ans;
    return 0;
}