题意理解 有 nnn 座城堡，小 C 要和 sss 个对手对战（方案必须相同）。占领第 iii 座城堡需要派遣严格大于对手两倍的士兵，得 iii 分。总士兵数不超过 mmm，求最大总得分。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思路分析 这是一个分组背包问题。 对于每座城堡 iii，小 C 有 s+1s+1s+1 种选择：击败 0,1,2,cdots,s0, 1, 2, \\cdots, s0,1,2,cdots,s 个对手。 预处理： 对于每座城堡，将 sss 个对手的派兵数排序。要击败派兵最少的 kkk 个对手，需要的士兵数是 2×sorted[k]+12 \times sorted[k] + 12×sorted[k]+1，得分是 k×ik \times ik×i。 分组背包： 每座城堡是一组，每组选一个方案（击败多少对手），求总得分最大。 设 dp[j]dp[j]dp[j] 表示：用 jjj 个士兵能获得的最大得分。 边界条件： * dp[0]=0dp[0] = 0dp[0]=0 答案： dp[m]dp[m]dp[m] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 参考代码