网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P11377
2024-12-10
题解:P11377 [GESP202412 七级] 武器购买
思路这是一个典型的背包问题。我们可以设\(dp_{j}\)为武器总强度为\(j\)的情况下的最小花费。于是,根据背包问题的模型我们就能得出:\[dp_j=\max_{1\lei\len}dp_{j-c_i}+p_i\]最终,答案就为第一个大于等于\(P\)的\(dp_j\)的下标\(j\)。时间复杂度为\(O(Tn