社区讨论

重要的核心!!!

P1064[NOIP 2006 提高组] 金明的预算方案参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m64isdjm
此快照首次捕获于
2025/01/20 12:02
去年
此快照最后确认于
2025/11/04 11:14
4 个月前
查看原帖
对于每件物品有4种情况可以讨论: (1)主件是否购买 (2)主件+附件1是否购买 (3)主件+附件2是否购买 (4)主件+附件1+附件2是否购买
因此状态转移方程为:
CPP
f[j] = max(f[j],f[j-主件价格]+主件价值,f[j-主件价格-附件1价格]+主件价值+附件1价值,f[j-主件价格-附件2价格]+主件价值+附件2价值,f[j-主件价格-附件1价格-附件2价格]+主件价值+附件1价值+附件2价值)
注意判断:要买的物品的价格<=j
/* 1.只要不超过N元钱就行
2.要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件
3.使每件物品的价格与重要度的乘积的总和最大 价值 = 价格 * 重要度 */

回复

2 条回复,欢迎继续交流。

正在加载回复...