tkdsheep-solution-0073

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

大菠萝2
人物有一个power属性，这个power是由他的技能等级以及身上带的护身符决定的
人物有多个技能，以及一些技能点，每个技能消耗一点技能点（升一级）可以增加固定power值，每个技能都有一个等级上限，当达到等级上限时就不能再加点了，但是会额外增加部分power值
然后人物可以带一些护身符，他库存里有m个护身符，装备可以带其中的n个
每个护身符都可以增加一些power值，并且有的护身符会使部分技能升一级，比如使技能3和技能4都升一级，但是技能不能超过等级上限，并且如果有多个护身符让同一个技能升级，那么这个技能也只会升1级
求怎么给技能加点以及护身符选哪些，使最终power最大
本题技能最多只有7种，可以分两步来做
第一步是一个dp，dp[i][j][mask]表示前i种护身符，选了其中j个护身符，技能被护身符加成的状态为mask的情况下，总power最大为多少
第二步就是如果分配技能点
如果技能没有满级的额外加成，那么肯定是优先升满power加成多的技能，如果要先加power加成少的技能，必定是要把这个技能加满得到它的额外加成
所以无论怎样，都一定是先加满一个技能再加满另一个技能，直到技能点不够加满一个技能
所以可以枚举每一个mask的dp状态，在这个状态的基础上再做7!的暴力枚举技能加点的顺序即可

大菠萝2

人物有一个power属性，这个power是由他的技能等级以及身上带的护身符决定的

人物有多个技能，以及一些技能点，每个技能消耗一点技能点（升一级）可以增加固定power值，每个技能都有一个等级上限，当达到等级上限时就不能再加点了，但是会额外增加部分power值

然后人物可以带一些护身符，他库存里有m个护身符，装备可以带其中的n个

每个护身符都可以增加一些power值，并且有的护身符会使部分技能升一级，比如使技能3和技能4都升一级，但是技能不能超过等级上限，并且如果有多个护身符让同一个技能升级，那么这个技能也只会升1级

求怎么给技能加点以及护身符选哪些，使最终power最大

本题技能最多只有7种，可以分两步来做

第一步是一个dp，dp[i][j][mask]表示前i种护身符，选了其中j个护身符，技能被护身符加成的状态为mask的情况下，总power最大为多少

第二步就是如果分配技能点

如果技能没有满级的额外加成，那么肯定是优先升满power加成多的技能，如果要先加power加成少的技能，必定是要把这个技能加满得到它的额外加成

所以无论怎样，都一定是先加满一个技能再加满另一个技能，直到技能点不够加满一个技能

所以可以枚举每一个mask的dp状态，在这个状态的基础上再做7!的暴力枚举技能加点的顺序即可