NENU 蓝桥杯训练赛(dp) 题解
A 糖果
思路：
f [ i ] [ j ] f[i][j] f[i][j] 表示前 i i i 个数 m o d mod mod k = = j k==j k==j 的最大值。
B 判断整除
思路：
f [ i ] [ j ] f[i][j] f[i][j] 表示前 i i i 个数 m o d mod mod k = = j k==j k==j 是否可行。
C 宠物小精灵之收服
思路：
f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 表示前 i i i 个精灵剩余精灵球为 j j j 剩余体力为 k k k 最多能捕获多少个精灵。
D 开餐馆
思路：
f [ i ] [ 0 / 1 ] f[i][0/1] f[i][0/1] 表示第 i i i 个餐馆选或者不选的最大利润。
E 非法二进制数
思路：
f
[
i
]
[
0
/
1
]
f[i][0/1]
f[i][0/1] 表示前
i
i
i 位是
0
0
0 或者
1
1
1 的合法二进制的方案数。
非法方案数 = 总方案数 - 合法方案数
F 工作城市分配
思路：
f [ i ] [ j ] f[i][j] f[i][j] 表示 i i i 个人去北京 j j j 个人去上海的满意度。
G 对局匹配
思路：
f [ i ] [ 0 / 1 ] f[i][0/1] f[i][0/1] 表示前 i i i 个人，第 i i i 个人匹配成功或者不成功的局数。
H 最长公共子序列
思路：
因为是全排列，所以数组中不会出现两个相同的数。求最长公共子序列可以转化为求最长上升子序列问题。
I 数字组合
思路：
二进制 + 暴力。
J 魔法宝石
思路：
01 01 01 背包。