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

题目链接：p14328

题意描述

有 $N$ 个糖果排成一列，每个糖果有一个美味度 $A_i$。需要选择糖果，使之满足限制：对于任意连续的 $K$ 个糖果，最多只能选择其中 $2$ 个。并在满足限制的条件下，最大化所选糖果的美味度总和。

数据范围：$2 \le K \le N \le 3000$

解题思路

动态规划

在写题的时候很容易想到要使用 $dp$，那怎么设计呢？发现选取 $i$ 的情况是由 $j \in [i-k+1,i-1]$ 转移得到，而对于 $dp[j]$ 我们选取其所有转移到 $j$ 的最大值。

状态定义

定义 $dp[i][j]$ 表示选择第 $i$ 个糖果，并且从第 $j$ 个位置转移过来的最大美味度总和。

同时定义 $ma_dp[i][j]$ 作为前缀最大值数组，用于优化时间复杂度，表示前 $j$ 个位置中最大的 $dp[i][j]$ 值。

并将 $dp[i][i]$ 初始化为 $wi[i]$，即选取一个点的情况。

状态转移

对于每个糖果 $i$，我们考虑：

选择第 $i$ 个糖果，并与之前某个糖果 $j$ 组合：

需要满足 $j$ 和 $i$ 的距离不超过 $K$（即 $i-k+1 \le j < i$），如果超过，直接取其最大值，因为我们可以中间不选。
转移方程为：$dp[i][j] = \max\limits_{1 \le k \le \min(j, i-K)} max_dp[j][k] + A_i$

前缀最大值优化

为了快速获取前 $j$ 个位置中的最大值，我们使用 $ma_dp[i][j]$ 数组：

$ma_dp[i][j] = ma_dp[j][pre]+wi[i]$，其中 $pre$ 是选完 $j$ 后最后合法的位置。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn=3e3+10;
constexpr int maxm=2e5+10;
constexpr int INF = 0x3f3f3f3f3f3f3f3f;int n,k;
int wi[maxn];
int dp[maxn][maxn]; // dp[i][j] i第个点，从j转移的最大值
int ma_dp[maxn][maxn]; // 前缀最大值数组signed main()
{scanf("%lld%lld",&n,&k);int ans=0;for(int i=1;i<=n;++i){scanf("%lld",wi+i);}for(int i=1;i<=n;++i){ dp[i][i]=wi[i];for(int j=i-k+1;j<i;++j){int pre=max(0LL,i-k);// 小于0不合法不转移if(pre){if(pre>j){pre=j;// 不想思考了，直接特判，pre>j意味着j可以任意选取，由于我们需要前面全部的可能，所以取j最大值}dp[i][j]=ma_dp[j][pre]+wi[i];}else {dp[i][j]=wi[i]+wi[j];// pre==0 直接算j和i的价值（因为是从j转移到i的）}ans=max(ans,dp[i][j]);}for(int j=1;j<=i;++j){ma_dp[i][j]=max(ma_dp[i][j-1],dp[i][j]);// 预处理ma_dp}}printf("%lld\n",ans);return 0;
}

复杂度分析

时间复杂度：$O(N^2)$，因为有两层循环分别遍历 $N$ 个糖果和最多 $K$ 个转移位置
空间复杂度：$O(N^2)$，用于存储 $dp$ 和 $ma_dp$ 数组

资讯详情

candy P14328: dp优化