Deep_Dark_FAntasy♂

线性dp、背包...

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

/ 注册

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

最长公共子序列LCS并输出LCS

LCS：设d(i,j)为A1,A2,...,Ai和B1,B2,...,Bj的LCS长度，则当A[i]=B[j]时，d(i,j)=d(i-1,j-1)+1,否则d(i,j)=max{d(i-1,j),d(i,j-1)},时间复杂度为O(nm),其中n和m分别是A和B的长度。输出LCS的思想其实就是倒过...

输出最长公共子序列

2020-07-22

1 662

石子合并2

先看题目：https://ac.nowcoder.com/acm/problem/50493题目描述：与石子合并1的规则相同，只不过所有石子现在围成了一个环形。解题思路：处理环有两种方法，一种是取模，另一种是序列加倍。序列加倍就是把‘1234’变成'12341234'使循环的完全可以用链的方法解决了...

取模石子合并环形区间dp 序列加倍

2020-06-23

0 686

石子合并(简单版)

先看题目：https://ac.nowcoder.com/acm/problem/51170题目描述：N堆石子排成一排，每次可以合并相邻的两堆，每次合并得分为合并的两堆石子之和，问把所有石子合成一堆的最小得分是多少？解题思路：区间dp入门题，dp[i][j]表示从i到j合并的最小得分，则可写出状态转...

区间dp

2020-06-23

0 762

简单瞎搞题

先看题目：https://ac.nowcoder.com/acm/problem/17193题目描述：略解题思路：暴力枚举总共有100^100次方种情况，考虑使用dp。那么状态定义为什么呢？如果定义为dp[i][j]表示前i项有没有构成j这个数字，那么状态转移方程就变得很麻烦了，首先，开个1e8的数...

bitset dp的优化

2020-06-22

0 522

迁徙过程中的河流

先看题目：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/16810题目描述：有一个导弹系统，每一发炮弹都不能高于前一发的高度。第一问是问能拦截多少导弹？第二问是问要拦截所有导弹最少需要多少套这样的导弹系统？解题思路：第一问就是求序列的最长不上升子序列。第二问我的思路是：整个...

nlogn优化 Dilworth定理最长上升子序列最长下降子序列

2020-06-19

0 503

过河卒

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