刷题总结2
_QWQ__QWQ_ · · 个人记录
同步于cnblogs
T1 AT_joisc2007_buildi ビルの飾り付け (Building)
简化题意
最长上升子序列模板
分析
O(n^2) 做法
考虑DP
- 定义状态：
dp_i 表示以i 结尾的最长上升子序列长度 - 确定答案：
\max{dp_i} - 状态转移：对于每个
a_i ： (1)当a_i>a_j(j<i) 从以第j 个数结尾的地方再接一个数，即dp_j+1 (2)自己单独成一个子序列 - 边界条件：
dp_i=1 (每个数都能单独成一个子序列)O(n\log n) 做法考虑贪心（往死里贪） 所以对于最大上升子序列，结尾元素越小，越有利于后面接上其他的数，也就可能变得更长 所以创建一个数组
c ，用来存贮现在的最长上升子序列中的元素 对于每个a_i ，可以在c 数组中找到一个第一个比他大的数，那么这个数就能替换掉c 数组中的那个数，而dp_i 的答案就是找到的数的下标，因为前面都是比他小的数，自然的，他也可以接在这些数后面 但是这样可能还是要扫一遍c 数组，但我们能发现，c 数组永远是单调递增的！所以使用二分大法，时间复杂度O(n\log n) P.S.：c 一定要初始化为无穷大，因为数要越小越好Code
link1 link2
T2 AT_abc281_d [ABC281D] Max Multiple
分析
- 定义状态：
dp_{i,j,p} 表示前i 个数，选了j 个，余数为p 时的最大和 - 答案：
dp_{n,k,0}(dp_{n,k,0}\geq0) ，否则为-1 - 方程：
（1）不选这个数:
dp_{i-1,j,p} （2）选这个数:dp_{i-1,j-1,(p-a_i)\mod d }+a_i - 边界：
dp_i=-\inf ，dp_{0,0,0}=0 Code
link
T3 AT_abc369_d [ABC369D] Bonus EXP
题意简化
有
- 放走他，获得
0 经验 - 击败他，获得
a_i 经验，特别的，如果这只怪兽是你击败的偶数只怪物，你还可以额外获得a_i 经验 求最后你能获得多少经验分析
- 定义状态：
dp_{i,0/1} 表示前i 个怪物，选了奇数/偶数个怪物的最大经验 - 答案
\max(dp_{n,0},dp_{n,1}) - 状态转移方程：
（1）选第
i 个怪物，且为奇数个：\max(dp_{i-1,0},dp{i-1,1}+a_i) （2）选第i 个怪物：\max(dp_{i-1,1},dp_{i-1,0}+2\times a_i) - 边界：由于
a 可能有负数，所以dp设为负无穷Code
link