BZOJ-3771. Triple

这题挺有意思的,来源是 SPOJ-TSUM,题意大概是,给出 n 个物品,第 i 个物品的价值为 x_i(0 < x_i \leq 4\cdot10^4),问在这 n 个物品中选出 1 个或 2 个或 3 个价值和是多少,对于每个价值求出方案个数,在这题中 (a, b)(b, a) 算作一种方案

例如有三个物品

x_1 x_2 x_3
1 2 3

选一个就可以得到 1, 2, 3 三种价值

选两个就可以得到 1+2, 1+3, 2+3 三种价值

选三个就可以得到 1+2+3 一种价值

所以最后答案就是

价值 1 2 3 4 5 6
方案数 1 1 2 1 1 1

(more…)

Read More