题解：UVA10482 The Candyman Can

jiqihang · 2024-12-28 21:51:42 · 题解

题目链接

UVA10482 The Candyman Can

题意

给你 n 个数，把这 n 个数分成三个部分，问总和最大与最小的差值最小是多少。

本题多测！！！

分析

由于 n \le 32，我们可以暴力枚举。

枚举前两个部分，第三个部分可以通过总和与前两个部分相减求出。

设一个 flag_{i,j}（i 为第一组的和，j 为第二组的和），第三组就是总和减去 i 和 j。

若 flag_{i,j} 满足，那么 flag_{i,j+a_i} 与 flag_{i+a_i,j} 满足，继续推即可。