题解：UVA10482 The Candyman Can

_WHX985_ · 2025-01-13 09:44:20 · 题解

前言

本题是一道英文题，所以在此放出翻译。

题目翻译

正文1

首先分析数据范围，因为 n\le32 所以说这道题可以考虑暴力 + 动态规划。

正文2

枚举方法只需要枚举两个堆，另一个堆只需用总数减前两堆的数量，我们假设总数为 num 第一堆为 α 第二堆为 β 则第三堆为 num-α-β。

正文3

主题思路 建立二维的的 dp 数组，第 α 行 β 列表示第一堆为 α 第二堆为 β 第三堆为 num-α-β 是否满足，推出当 dp 数组的 x 行 y 列满足，本行的 y 加上第 x 颗糖果的重量列也满足且本列的 x 加上第 x 颗糖果的重量满足。

正文4

最后用上文的发现暴力枚举即可求出答案。

后记

感谢 zhouzhengxuan 提供的翻译。