楼教主男人八题(第一题)
楼天城,1986 年出生,高中毕业于杭州十四中。2004 年保送进清华大学计算机系。2008年进入姚期智院士领导的清华大学理论计算机中心攻读博士。2017年初,创办小马智行(pony.ai)。楼天城是中国公认的大学生计算机编程第一人,经常以一人单挑一个队,在 ACM 界无人不晓其大名,人称“楼教主”。
2004年,楼教主在 POJ(http://poj.org/) 举办了第一场"是男人就过八题"的主题比赛。2018年,举办了第二场。绝大多数参赛选手只过了一道题,赛后纷纷表示做男人真难。
![](https://filescdn.proginn.com/cd771afae7e72c150fd27676df8dbf9a/299f4e2aad9134cdbde9bb5d3251c957.webp)
![](https://filescdn.proginn.com/398499b2d825a87ceb2a328f63be46df/a046ef801aa2a555e7a924fb99444ece.webp)
这是2004年的题目,已经十七年了,最多的一道通过了 6790 次,最少的仅有 582 次。
![](https://filescdn.proginn.com/bd9c913fc47569d767608792c60ea38a/c430a10db16cd94c62dc1ff3d7b3c001.webp)
接下来让我们按照通过人数从高到低,依次体验下。今天先来看下 「1742 Coins」 这道题。
题目链接
http://poj.org/problem?id=1742
题目描述
People in Silverland use coins. They have coins of value Silverland dollar. One day Tony opened his money-box and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m
. But he didn't know the exact price of the watch.
You are to write a program which reads and corresponding to the number of Tony's coins of value then calculate how many prices(form 1
to m
) Tony can pay use these coins.
输入
The input contains several test cases. The first line of each test case contains two integers n
(),m
(m\le 100000
).
The second line contains 2n
integers, denoting ().
The last test case is followed by two zeros.
输出
For each test case output the answer on a single line.
样例输入
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
样例输出
8
4
样例解释
样例共输入了两组数据,第一组:
3 10
1 2 4 2 1 1
总共有三种硬币:
2 个面值 1 的。 1 个面值 2 的。 1 个面值 4 的。
拢共可以拼出8种总面值:
总面值 1 :1 总面值 2 :1+1; 2 总面值 3 :1+2 总面值 4 :1+1+2; 4 总面值 5 :1+4; 总面值 6 :1+1+4; 2+4 总面值 7 :1+2+4 总面值 8 :1+1+2+4
第二组:
2 5
1 4 2 1
总共可以拼出五种:
总面值 1 :1 总面值 2 :1+1 总面值 4 :4 总面值 5 :1+4 总面值 6 :1+1+4
但是,不超过 5的只有四种。所以答案为 4。
解题思路
知识点:「多重背包」
时间复杂度:
该场比赛的签到题。直接套上「多重背包」模板即可。下面简单介绍下多重背包。
多重背包的题目场景大都可抽象为:现有一个体积为 的背包,以及若干种物品,每种物品的重量为,体积为 ,数量为 。问,该背包最多能放入多少重量的物品。
还有些较为简单的场景,会省略物品的重量属性,即物品只有体积和数量,问有多少种总体积不同的放置方案。
该题就是第二种场景:
手表的价格上限 m
,可以视作背包的体积 。硬币的面值可以视作物品的体积。 硬币的数量就是物品的数量。
那么问题「n种硬币能凑出多少种不同的面值」,等价的变成了「n种物品能凑出多少种不同的体积」。
我们不妨把拼凑出体积 i 的方案表示为集合 。很显然, 是一个空集。接下来,以 为基础,构造 的 。
不妨举个具体的例子:,且有两种物品:
第一种:1 个体积为 4 的物品。 第二种:2 个体积为 2 的物品。
首先,向 放入一个体积为 4 的物品,得到:
现在我们有了三个集合:
继续处理第二种物品,以上述三个集合为基础,放入第一个 2:
接着,向 中放入第二个 2。
为何不用再尝试一次呢?因为两个体积为 2 的物品无差别,这样重复尝试无意义~
现在拼出了五种总体积,甚至有些体积有多种拼凑方案:
用代码实现一下上述构造过程:
// 只关心Si是否存在,所以用 bool 数组表示。
// true 为存在,false为不存在。
// 初始时,只有S0存在
bool S[V+1] = {false};
S[0] = true;
// 枚举物品种类
for (int i = 0; i < goods.size(); i++) {
const auto &g = goods[i];
// 第i种物品的体积为 vol,数量为 num
for (int j = 0; j < g.num; j++) {
for (int k = V; k >= g.vol; k--) {
// Sk 为true可分为两种情形:
// 1. 在此之前已经拼凑出 k 了。
// 2. 已拼出了 S[k-vol],放入一个 vol 即得到 S[k]。
S[k] = S[k] || S[k-g.vol];
}
}
}
上述代码的时间复杂度为,这其实是把多重背包当错01背包处理。
接下来,给出 ,即 的思路。首先,来看看完全背包的写法:
// 只关心Si是否存在,所以用 bool 数组表示。
// true 为存在,false为不存在。
// 初始时,只有S0存在
bool S[V+1] = {false};
S[0] = true;
// 枚举物品种类
for (int i = 0; i < goods.size(); i++) {
const auto &g = goods[i];
// 完全背包不会限制物品数量
for (int k = g.vol; k <= V; k++) {
S[k] = S[k] || S[k-g.vol];
}
}
在完全背包的基础上,增加数组 完成对物品数量的限制。 表示 中当前物品的数量,当 有多种方案时,应选取 最小的方案。
// 只关心Si是否存在,所以用 bool 数组表示。
// true 为存在,false为不存在。
// 初始时,只有S0存在
bool S[V+1] = {false};
S[0] = true;
// 枚举物品种类
for (int i = 0; i < goods.size(); i++) {
const auto &g = goods[i];
memset(used, 0, sizeof(used));
for (int k = g.vol; k <= V; k++) {
if (!S[k] && S[k-g.vol] && used[k-g.vol] < g.num) {
S[k] = true;
used[k] = used[k-g.vol] + 1;
}
}
}
下面试完整的 Accepted 的代码。
#include
#include
#include
using namespace std;
int val[100];
int cnt[100];
bool pack[100001];
int used[100001];
int main() {
int n, m;
while(scanf("%d %d", &n, &m), n != 0 && m != 0) {
for (int i = 0; i < n; i++) {
scanf("%d", val+i);
}
for (int i = 0; i < n; i++) {
scanf("%d", cnt+i);
}
memset(pack, 0, sizeof(bool)*(m+1));
pack[0] = true;
for (int i = 0; i < n; i++) {
memset(used, 0, sizeof(int)*(m+1));
for (int j = val[i]; j <= m; j++) {
int pre = j - val[i];
if (pack[pre] && pack[j] == false && used[pre] < cnt[i]) {
pack[j] = true;
used[j] = used[pre] + 1;
}
}
}
int anw = 0;
for (int i = 1; i <= m; i++) {
anw += pack[i];
}
printf("%d\n", anw);
}
return 0;
}