AtCoder Beginner Contest 286 题目讲解
蒟蒻来讲题，还望大家喜。若哪有问题，大家尽可提！
Hello, 大家好哇！本
初中生蒟蒻
今天以AtCoder Beginner Contest 286的D题——Money in Hand为例，给大家讲解一下判断图中存在闭环的常用方法！
===========================================================================================
原题
Problem Statement
Takahashi has
N
N
N
kinds of coins; specifically, for
1
≤
i
≤
N
1\leq i\leq N
1
≤
i
≤
N
, he has
B
i
B_{i}
B
i
coins worth
A
i
A_{i}
A
i
yen (the currency in Japan) each.
Determine if Takahashi can pay exactly
X
X
X
yen (without change) with the coins he currently has.
Constraints
-
1≤
N
≤
≤
50
1\leq N≤\leq 50
1
≤
N
≤≤
50
-
1≤
X
≤
1
0
4
1\leq X\leq 10^4
1
≤
X
≤
1
0
4
-
1≤
A
i
≤
100
1\leq A_{i}\leq 100
1
≤
A
i
≤
100
-
1≤
B
i
≤
50
1\leq B_{i}\leq 50
1
≤
B
i
≤
50
-
Ai
A_{i}
A
i
are pairwise distinct. - All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X
A1 B1
A2 B2
⋮
AN BN
Output
Print Yes if Takahashi can pay exactly
X
X
X
yen with the coins he currently has; print No otherwise.
Sample Input 1
2 19
2 3
5 6
Sample Output 1
Yes
Takahashi has three
2
2
2
-yen coins and six
5
5
5
-yen coins. He can use two
2
2
2
-yen coins and three
5
5
5
-yen coins to pay exactly
2
×
2
+
5
×
3
=
19
2×2+5×3=19
2
×
2
+
5
×
3
=
19
yen. Thus,
Y
e
s
Yes
Y
es
should be printed.
Sample Input 2
2 18
2 3
5 6
Sample Output 2
No
There is no combination of the coins that he can use to pay exactly
18
18
18
yen. Thus,
N
o
No
N
o
should be printed.
Sample Input 3
3 1001
1 1
2 1
100 10
Sample Output 3
Yes
He need not use all kinds of coins.
思路
这道题真的挺简单，就是一个裸的恰好装满的多重背包问题，所以直接套模板即可。我们知道多重背包有三种解决方式，由于这道题数据比较少，三种都能用！（因为大家应该都会了，所以在此不一一讲解，若有不会的，私聊我，我一定竭尽所力的讲解）
三种代码
N为物品数量，V为物品最多的重量，S为物品的个数
第一种（时间复杂度：
O
(
N
×
V
×
S
)
O(N\times V\times S)
O
(
N
×
V
×
S
)
）
#include <bits/stdc++.h>
using namespace std;
const int M = 1e4 + 10;
int n, x;
int w[M], s[M];
bool dp[M];
int main()
{
cin.tie(0);
ios :: sync_with_stdio(0);
cin >> n >> x;
for (int i = 1; i <= n; i ++)
cin >> w[i] >> s[i];
dp[0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = x; j >= 0; j --)
for (int k = 1; k <= s[i] && k * w[i] <= j; k ++)
dp[j] |= dp[j - w[i] * k];
if (dp[x]) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
第二种二进制优化（时间复杂度：
O
(
N
×
V
×
l
o
g
(
S
)
)
O(N\times V\times log(S))
O
(
N
×
V
×
l
o
g
(
S
))
）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e4 + 10;
int n, w;
int wt[N], vl[N], sz[N];
int f[N];
int main()
{
cin >> n >> w;
int ww, vv, ss;
int cnt = 0;
for (int i = 1; i <= n; i ++)
{
cin >> ww >> ss;
int k = 1;
while (k <= ss)
{
wt[++ cnt] = ww * k;
ss -= k;
k *= 2;
}
if (ss)
{
wt[++ cnt] = ww * ss;
}
}
f[0] = 1;
for (int i = 1; i <= cnt; i ++)
for (int j = w; j >= wt[i]; j --)
f[j] |= f[j - wt[i]];
cout << ((f[w]) ? "Yes" : "No") << endl;
}
第三种单调队列优化（时间复杂度：
O
(
N
×
V
)
O(N\times V)
O
(
N
×
V
)
）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e4 + 10;
int n, W;
int q[N], g[N], f[N];
int main()
{
cin >> n >> W;
f[0] = 1;
for (int i = 0; i < n; i ++ )
{
int w, v, s;
cin >> w >> s;
memcpy(g, f, sizeof f);
for (int j = 0; j < w; j ++)
{
int h = 0, t = -1;
for (int k = j; k <= W; k += w)
{
if (h <= t && k - s * w > q[h]) h ++;
while (h <= t && g[q[t]] <= g[k]) t --;
if (h <= t) f[k] |= g[q[h]];
q[++ t] = k;
}
}
}
(f[W]) ? puts("Yes") : puts("No");
}
今天就到这里了！
大家有什么问题尽管提，我都会尽力回答的！最后，除夕夜祝大家新年快乐！
吾欲您伸手，点的小赞赞。吾欲您喜欢，点得小关注！