Deep_Dark_FAntasy♂

线性dp、背包...

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 未归档(176) 深度优先搜索、广度优先搜索、搜索剪枝(8) 题解(12)

/ 注册

全部文章 / 线性dp、背包问题、区间dp （共15篇）

合唱队形

先看题目：https://ac.nowcoder.com/acm/problem/16664题目描述：n个人为了排成最长的合唱队形需要多少人出列？(合唱队形是指T1 < T2 < ... < Ti > Ti+1 > ... > Tn)解题思路：先从前往后通过求最长...

最长上升子序列最长下降子序列动态规划

2020-06-18

0 858

金明的预算方案

先看题目：https://ac.nowcoder.com/acm/problem/16671题目描述：从m个物品中挑选，m个物品中有主件有附件，要求挑选附件的时候必须挑选其所属的主件(每个主件可以有0/1/2个附件)，希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大...

就地滚动动态规划 01背包

2020-06-18

0 672

开心的金明

先看题目：https://ac.nowcoder.com/acm/problem/16666题目描述：从m个物品中挑选，希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。解题思路：01背包，只不过这里dp[][]记录的是价格与重要度的乘积而不是能够塞下物品的数量代码...

动态规划 01背包

2020-06-18

0 426

滑雪

先看题目：https://ac.nowcoder.com/acm/problem/105685题目描述：一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。任选一点作为起点，问最长滑雪区域的长度。解题思路：动态规划入门题，结合此题回顾一下动态规划的一般步骤。first ，首先结合原问题和...

记忆化搜索动态规划

2020-06-18

0 567

采药

先看题目：https://ac.nowcoder.com/acm/problem/16650题目描述：给出能够用来采药的时间T和山洞里的草药的数目，问在规定的时间内，可以采到的草药的最大总价值。解题思路：01背包问题，定义状态dp[i][j]为前i个物品，花费时间在j以内，可获得的最大价值。状态转移...

就地滚动动态规划 01背包

2020-06-18

0 599