DP问题如没思路，请熟练掌握DFS取保底分！配合记忆化效果更佳

P13015 [GESP202506 六级] 学习小组 题解

题意

把n个同学划分成若干小组。一个小组人数为k，可以获得价值a_k。所有人必须分组，求总积极度的最大值。
n <= 1000。

思路：完全背包DP

  1. dp[j]表示把j个同学分组能够得到的最大总价值。
  2. len代表一组的人数（物品体积），选len个人为一组可以获得价值a[len]。同一分组大小可以选多次，属于完全背包模型。
  3. 状态转移：dp[j] = max(dp[j], dp[j‑len] + a[len])
  4. 外层循环枚举小组长度len，内层从小到大枚举总人数j，执行完全背包转移。

核心原理：
将分组等价于完全背包：“选一组len人”当作物品，体积len，价值a[len]，装满容量n，求最大价值。

样例1：
n=4，a=[1,5,6,3]
最优划分：2+2，5+5=10，输出10。

实现要点：
完全背包j从小到大循环；dp数组求最大值；最终输出dp[n]。

P17012 [GESP202606 六级] 条形蛋糕 题解

题意

总长度n的蛋糕，可以切成若干整数长度小块，长度i的蛋糕售价p_i。求切割之后总售价的最大值。
n <= 1000。

思路：完全背包DP

  1. dp[j]代表总长度为j的蛋糕可以卖出的最大价钱。
  2. len代表切出一块蛋糕的长度，体积len，价值a[len]；同一种长度可以切多段，属于完全背包模型。
  3. 状态转移：dp[j] = max(dp[j], dp[j-len] + a[len])
  4. 外层枚举蛋糕块长度len，内层j从小到大遍历总长度，执行完全背包转移。

核心原理：
蛋糕切割等价完全背包，把“切一段len长度”看作物品，装满总长度n，求最大价值。可以不切，整块卖出。

样例1：
n=4，价格 1 5 8 9。最优分割2+2，5+5=10，输出10。

实现要点：
完全背包内层循环j从小到大；dp求最大值；输出dp[n]。

P14920 [GESP202512 六级] 道具商店 题解

题意

n件道具，每件只能买一次。第i件加a_i攻击力，花费c_i金币。拥有k金币，求最大攻击力。
n <= 500，a_i <=500，但是k、c_i可以到10^9，普通以金币作为容量的01背包无法开数组。

  • 如果以金币为背包，求最大攻击力，背包大小k上限1e9，实在没思路可以按60%数据去做，上限设置500，得60分。

思路：价值反向01背包

  1. 总攻击力上限：na_i = 500500 = 250000。把攻击力当作dp的下标。
  2. dp[j]表示获得j点攻击力，需要花费的最小金币数。
  3. 01背包倒序循环：dp[j] = min(dp[j], dp[j-a[i]] + c[i])
  4. 遍历全部攻击力j，如果dp[j] <= k，说明金币足够，更新最大答案ans。

核心原理：
金币数值太大不能做背包容量；攻击力总和很小，转换维度，求达成该攻击力最少花钱，再判断是否在金币上限以内。

样例1：
n=3，k=5。三件道具(99,1) (33,2) (11,3)。
选前两件，攻击力132，花费金币 1+2=3 <=5，输出132。

实现要点：
dp初始赋值极大值，dp[0]=0；01背包倒序；最后扫描所有攻击力取合法最大值。

B3873 [GESP202309 六级] 小杨买饮料 题解

题意

N种饮料，每种最多买1瓶。每瓶有花费c_i，容量l_i。选出若干瓶，总容量大于等于L，求最小花费。无解输出no solution。
N <= 500，L <= 2000。

思路：01背包反向维度

  1. dp[j]代表凑出j毫升容量，需要的最小花费。
  2. 每件饮料只能选一次，标准01背包，j倒序遍历。
  3. 因为只需要至少L毫升，超过L的容量统一可以视作L，数组可以做截断优化。
  4. 遍历所有 j >= L 的状态，取dp[j]的最小值作为答案。
  5. 如果最小值仍然是极大值，代表无解。

核心原理：
目标不是限制总钱数，要最小化花费；把容量作为dp下标，记录达到该容量最少花多少钱。01背包模型。

样例1：
n=5，L=100。选1、2、4号饮料，总容量110，花费9，输出9。

实现要点：
dp数组初始无穷大，dp[0]=0；01背包倒序；最后扫描大于等于L的容量取最小代价。

B3873 [GESP202309 六级] 小杨买饮料 题解

题意

N种饮料，每种最多买1瓶。每瓶有花费c_i，容量l_i。选出若干瓶，总容量大于等于L，求最小花费。无解输出no solution。
N <= 500，L <= 2000。

思路：01背包反向维度

  1. dp[j]代表凑出j毫升容量，需要的最小花费。
  2. 每件饮料只能选一次，标准01背包，j倒序遍历。
  3. 因为需要至少L毫升，背包容量不能真设置为L，可以取所有饮料总量。
  4. 遍历所有 j >= L 的状态，取dp[j]的最小值作为答案，即满足L容量的最低价格。
  5. 如果最小值仍然是极大值，代表无解。

核心原理：
目标不是限制总钱数，要最小化花费；把容量作为dp下标，记录达到该容量最少花多少钱。01背包模型。

样例1：
n=5，L=100。选1、2、4号饮料，总容量110，花费9，输出9。

实现要点：
dp数组初始无穷大，dp[0]=0；01背包倒序；最后扫描大于等于L的容量取最小代价。

P10721 [GESP202406 六级] 计算得分 题解

题意

字符串里有连续拼接的abc片段，k个连续abc可以选择按a_k得分；连续k个abc也可以拆成多段分别计分。字符不能重复使用，求整个字符串最大总得分。
n <= 20，m <= 100000。

  • 这道题分两部分，一是背包问题，即求出不同连续abc个数能获得的最高分数，二是处理字符串，按连续abc个数做桶计数。

思路：完全背包DP

  1. 字符串切分预处理
    逐个下标i扫描字符串，判断从i开始是否为abc。
    如果匹配成功，就向后嵌套循环统计右连续多少组abc（每次跳3位），直到不再匹配abc为止。
    得到这一段连续abc的总组数t，cnt[t]++；
    i跳到这段的末尾，避免重复扫描字符。不属于abc的字符直接跳过。
例子：dabcabcabcabz，识别出连续3组abc，cnt[3]++。
  1. dp[k]代表：一段一共有k个连续abc时，可以拿到的最大分数。
  2. dp转移为完全背包：dp[j] = max(dp[j], dp[j‑i] + b[i])。i代表选取i个abc作为一组获得b[i]分，可以拆分。
  3. 遍历每一段长度t，该段贡献 cnt[t] * dp[t]，全部累加得到最终答案。

核心原理：
对于一段连续k个abc，允许任意拆分；求拆分后的最大价值等价完全背包；不同连续abc片段互相独立，分别计算再求和。

样例1：
n=3，计分3 1 2。字符串有一段连续3个abc。
dp[1]=3，dp[2]=max(b[2],dp[1]+dp[1])=max(1,6)=6，dp[3]=max(b[3],dp[2]+dp[1]) = max(2, 6+3)=9。输出9。

实现要点：
预处理切出连续abc块，扫描完成后i要跳转，不能i++逐个走，否则会重复处理；完全背包算出每个长度的最优得分；各段结果相乘累加；字符串规模大，预处理不能暴力。

P14075 [GESP202509 六级] 划分字符串 题解

题意

把字符串切分成若干子串，每个子串内部字母不能重复。长度为i的子串价值为a_i，求划分后的总价值最大值。
n <= 100000；因为只有26个小写字母，合法子串最长不会超过26。

思路：线性DP + 字符集合限制

  1. dp[i]：字符串前i个字符划分完成可以得到的最大总价值。
  2. 初始：dp[0]=0；dp[i]至少可以把第i位单独切一段：dp[i] = dp[i-1] + ar[1]。
  3. 倒向枚举j，从i往左边拓展子串 [j,i]；用vis数组标记字符是否出现。
  4. 如果遇到重复字符直接break（再往左依然会包含该重复字符，不再合法）。
  5. 当前子串[j,i]合法，则状态转移：dp[i] = max(dp[i], dp[j-1] + ar[i-j+1])。
  6. 答案为dp[n]。

核心原理：
小写字母一共只有26种，内层循环最多跑26次；总时间复杂度 O(n*26)，可以通过n=1e5。一旦出现重复字母，向左延伸的所有区间全部非法，直接break剪枝。

样例1：
n=6，字符串street，价值2 1 7 4 3 3。
最优划分 str + e + e + t；长度3+1+1+1，7+2+2+2 =13，输出13。

实现要点：
内层循环最多26轮，不能无脑循环到1；遇到重复字符立刻break；dp要用long long，a_i可以到1e9。

P10108 [GESP202312 六级] 闯关游戏 题解

题意

一共N关，处在x关，选通道a_i，跳到 x+a_i 关；离开s关可以拿到b[s]分数。起点在0关，一旦位置>=N就算通关。求通关可以拿到的最大总分。
注意b[s]可以为负数。N <= 10000，M <= 100。

思路：线性DP

  1. dp[i]：到达第i关时，已经累计得到的最大分数。
  2. dp数组初始负无穷，dp[0]=0，代表初始在0关，得分为0。

  3. 状态转移：如果从x关，走通道a[j]跳到i，那么 i = x + a[j]，等价 x = i - a[j]。
    当x合法(0 ≤ x < N)，dp[i] = max(dp[i], dp[x] + b[x])

    离开x关卡，才加上b[x]的分数。
  4. 只要位置i >= N就视为通关；因此收集所有 i ≥ N 的dp[i]取最大值就是答案。
  5. 数组开到2*N，防止跳跃越界，容纳通关的位置。

核心原理：
DP表示到达某一关的最大得分；每个位置由前面若干关卡跳跃转移而来；只要跳到大于等于N的位置即结束，取这些状态的最优值。部分b是负数，不能贪心，必须DP。

样例1：
N=6，通道{2,3}，b数组：1 0 30 100 30 30
路线：0 →3 →5 →≥6。得分 b[0]+b[3]+b[5] = 1+100+30 =131。输出131。

实现要点：

  • dp初始为负无穷，区分不可达状态；
  • 分数是离开x关才加上b[x]，不是到达i；
  • 最后遍历所有≥N的位置求最大值；
  • 使用long long，b可以负数，注意INF边界。

P15800 [GESP202603 六级] 选数 题解

题意

有数组a、b，挑选若干下标，下标严格递增；选中位置p_i之后，下一个选中下标必须≥p_i + b[p_i]。求选出a值总和的最大值。
n ≤ 100000。

思路1：倒推最优DP（正解 O(n)）

  1. dp[i]：从下标i到n这个区间，能够取到的最大总和。
  2. 边界：dp[n+1]=0，超出数组范围，没有数字可以选，收益为0。

  3. 对于位置i有两种决策：

    • 不选i：那么从i位置开始的最大收益等于 dp[i+1]
    • 选i：拿到a[i]，下一个可以选的位置至少是 next_pos = i + b[i]；如果next_pos超过n，则直接跳到n+1。总收益 a[i] + dp[next_pos]
  4. 状态转移：dp[i] = max(dp[i+1], a[i] + dp[next_pos])
  5. 从后往前倒序遍历，答案为dp[1]。

核心原理：
倒序DP，每个点只有选/不选两种分支；不需要循环找前面的点，O(n)时间复杂度，可以处理n=1e5。选完i之后直接跳到强制的下一个起点，不用枚举中间所有下标。

样例1：
n=4
a = [1,2,3,4]
b = [3,3,1,1]
i=4：next_pos=4+1=5，dp[4]=max(dp[5],4+dp[5])=4
i=3：next_pos=3+1=4，dp[3]=max(dp[4],3+dp[4]) = max(4,7)=7
i=2：next_pos=2+3=5，dp[2]=max(dp[3],2+0)=max(7,2)=7
i=1：next_pos=1+3=4，dp[1]=max(dp[2],1+dp[4]) = max(7, 1+4)=7
输出7。最优方案选3、4，3+4=7。

实现要点：

  1. 必须倒序循环；边界dp[n+1]=0；
  2. next_pos超过n的时候统一赋值为n+1；
  3. 使用long long，a_i可达1e9；
  4. O(n)，适合1e5规模。

思路2：暴力DP（部分分，O(n²)，仅n≤1000可过）

状态定义

dp[i]：前i个位置，第i位必须选时，能得到的最大a总和。
最终答案：max(dp[1],dp[2],…,dp[n])，可以以任意位置作为最后一个选中元素。

转移逻辑

  1. 如果强制选i：

    • 可以前面什么都不选：dp[i] = a[i]
    • 在i前面找一个j，满足 j + b[j] ≤ i，也就是选完j之后允许选i。
      dp[i] = max(dp[i], dp[j] + a[i])
  2. j需要遍历全部1~i‑1，双层循环。

思路说明

  1. 状态含义：dp[i]规定i必须选，方便转移；
  2. 内层j循环枚举上一个选的位置，判断条件j+b[j] ≤ i；
  3. 复杂度O(n²)，n=1000大约1e6次运算可以跑过；n=1e5会1e10次运算直接超时，只能拿部分分；
  4. 对比正解：暴力是“向前找合法j”；正解倒推DP直接算出选i之后直接跳到哪，省去枚举j，优化到O(n)。

P11963 [GESP202503 六级] 环线 题解

题意

环形数组，选取一段不重复经过车站的连续区间（环上子段），求子段和的最大值。子段至少包含1个元素。
n ≤ 2e5，元素可以为负数。

思路：环形最大子段和（环形Kadane）

  1. 普通最大子段（不跨环）：标准Kadane算法，dpMax[i] = max(a[i], dpMax[i‑1]+a[i])，得到max_sub。

  2. 如果最优子段跨过环的首尾：等价于「总和减去中间最小子段」。

    • sum为全部数组总和；
    • dpMin求最小子段和min_sub；跨环最大值 = sum - min_sub。
  3. 特殊边界：全部数字都是负数，此时不能选整环（sum‑min_sub会把所有负数全部选上），直接输出最大的单个元素max_sub。
  4. 答案：max(max_sub, sum‑min_sub)，当max_sub<0直接输出max_sub。

核心原理：
环上连续区间只有两种情况
① 区间没有绕环：普通最大子段和；
② 区间绕环首尾相连：等于总和挖掉中间一段最小的子段。

实现要点：

  1. dpMax维护以i结尾最大子段；dpMin维护以i结尾最小子段；
  2. 必须处理全负数的边界：如果max_sub<0，直接输出max_sub，不能用sum‑min_sub；
  3. 使用long long，a_i可达‑1e9，会爆int；
  4. O(n)时间，适配2e5。

补充：暴力部分分思路（O(n²)，n≤2000）

状态：把数组复制一倍破环成链a[1…2n]，枚举起点s，向后枚举长度len(1~n)，累加求和，记录最大值。
n=2000时4e6运算可过；n=2e5超时，可拿部分分。

// 暴力部分分示例
long long ans = -1e18;
for(int s=1;s<=n;s++){
    long long cur=0;
    for(int len=0;len<n;len++){
        int pos = s+len;
        if(pos>n) pos-=n;
        cur += a[pos];
        ans = max(ans,cur);
    }
}
cout<<ans;

标签: none

评论已关闭