Deep_Dark_FAntasy♂

线性dp、背包...

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

/ 注册

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

迁徙过程中的河流

先看题目：https://ac.nowcoder.com/acm/contest/5968/C题目描述：n个人通过小船渡河，小船每次只能运两人，渡河时间等于两人渡河最慢的那个的时间，(小船要考虑有人划回来),问最少花费多长时间能够把n个人送到对岸？解题思路：先考虑范围小一点的时候，n==1，n==2...

动态规划思维

2020-06-21

0 507

古老的牛市，遗迹的天梯

先看题目：https://ac.nowcoder.com/acm/contest/5968/A题目描述：有n级台阶，在i级台阶可以走到i+1级台阶(仅h[i+1] == h[i]+1)时，也可以往下一级台阶到i-1级。如果连续下降k级台阶到达了第i级台阶可以上升到高度小于等于h[i]+2^k的任何一...

n^2dp 动态规划思维

2020-06-20

0 582

牛牛的旅游纪念品

先看题目：https://ac.nowcoder.com/acm/contest/5968/E题目描述：n个物品中挑选m个物品，任意两个物品的位置差大于等于k，求最大受欢迎度。解题思路：背包问题，让求n个物品中挑m个物品的最大受欢迎度，跟据题意，设f[i][j]是前i个物品挑选j个的最大受欢迎度，转...

背包问题动态规划编程实现

2020-06-20

0 615

「木」迷雾森林

先看题目：https://ac.nowcoder.com/acm/problem/53675题目描述：给出一个m*n的地图，标0的可以走，标1的不能走。问从(m,1)点开始走到(1,n)点有多少条路径？解题思路：与过河卒那题一样的解法，这里就不再多说了。不同之处在于枚举方向跟据题意需要变化。数据量...

动态规划

2020-06-19

0 434

过河卒

先看题目：https://ac.nowcoder.com/acm/problem/16708题目描述：小卒从(0,0)点出发，不能通过象的控制点，问小卒到达(n,m)的路径有几条？解题思路：dp[i][j]定义为从(0,0)到(i,j)的路径数,dp[i][j]=dp[i-1][j]+dp[i][j...

动态规划

2020-06-18

0 483

合唱队形

先看题目：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