刷题总结2

同步于cnblogs

T1 AT_joisc2007_buildi ビルの飾り付け (Building)

简化题意

分析

$O(n^2)$做法

1. 定义状态：$dp_i$表示以$i$结尾的最长上升子序列长度
2. 确定答案：$\max{dp_i}$
3. 状态转移：对于每个$a_i$： (1)当$a_i>a_j(j<i)$从以第$j$个数结尾的地方再接一个数，即$dp_j+1$ (2)自己单独成一个子序列
4. 边界条件：$dp_i=1$(每个数都能单独成一个子序列)

$O(n\log n)$做法

Code

link1 link2

T2 AT_abc281_d [ABC281D] Max Multiple

分析

1. 定义状态：$dp_{i,j,p}$表示前$i$个数，选了$j$个，余数为$p$时的最大和
2. 答案：$dp_{n,k,0}(dp_{n,k,0}\geq0)$，否则为$-1$
3. 方程： （1）不选这个数:$dp_{i-1,j,p}$ （2）选这个数:$dp_{i-1,j-1,(p-a_i)\mod d }+a_i$
4. 边界：$dp_i=-\inf$，$dp_{0,0,0}=0$

Code

link

T3 AT_abc369_d [ABC369D] Bonus EXP

题意简化

1. 放走他，获得$0$经验
2. 击败他，获得$a_i$经验，特别的，如果这只怪兽是你击败的偶数只怪物，你还可以额外获得$a_i$经验 求最后你能获得多少经验

分析

1. 定义状态：$dp_{i,0/1}$表示前$i$个怪物，选了奇数/偶数个怪物的最大经验
2. 答案$\max(dp_{n,0},dp_{n,1})$
3. 状态转移方程： （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)$
4. 边界：由于$a$可能有负数，所以dp设为负无穷

Code

link

还有两题有时间补上