题目地址:
https://www.luogu.com.cn/problem/CF189A
题面翻译: 给一长度为
n
n
n的缎带,要求将其剪成若干长度为
a
,
b
,
c
a,b,c
a,b,c的缎带,且缎带数量尽可能多。
输入格式: 输入仅一行,四个正整数
n
,
a
,
b
,
c
(
n
,
a
,
b
,
c
≤
4000
)
n,a,b,c(n,a,b,c≤4000)
n,a,b,c(n,a,b,c≤4000)。
输出格式: 输出仅一行,即缎带数量的最大值。
题目描述: Polycarpus has a ribbon, its length is
n
n
n . He wants to cut the ribbon in a way that fulfils the following two conditions: After the cutting each ribbon piece should have length
a
a
a ,
b
b
b or
c
c
c . After the cutting the number of ribbon pieces should be maximum.
Help Polycarpus and find the number of ribbon pieces after the required cutting.
输入格式: The first line contains four space-separated integers
n
n
n ,
a
a
a ,
b
b
b and
c
c
c
(
1
≤
n
,
a
,
b
,
c
≤
4000
)
(1\le n,a,b,c\le 4000)
(1≤n,a,b,c≤4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers
a
a
a ,
b
b
b and
c
c
c can coincide.
输出格式: Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.
完全背包问题,设
f
[
k
]
[
n
]
f[k][n]
f[k][n]为只考虑前
k
k
k种长度的情况下,长
n
n
n的缎带最多能切成多少段,可以按照最后一段切出的长度是否是
a
[
k
]
a[k]
a[k]来分类,如果不是,则最多
f
[
k
−
1
]
[
n
]
f[k-1][n]
f[k−1][n];如果是,则最多
f
[
k
]
[
n
−
a
[
k
]
]
f[k][n-a[k]]
f[k][n−a[k]],取最大即可。需要注意在递推的时候,一定要保证方案存在。代码如下:
#include
#include
using namespace std;
const int N = 4010;
int n, a[4];
int f[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= 3; i++) scanf("%d", &a[i]);
memset(f, -1, sizeof f);
f[0] = 0;
for (int i = 1; i <= 3; i++)
for (int j = a[i]; j <= n; j++)
// 当方案存在的时候才递推
if (~f[j - a[i]])
f[j] = max(f[j], f[j - a[i]] + 1);
printf("%d\n", f[n]);
}
时空复杂度
O
(
n
)
O(n)
O(n)。
参考阅读
发表评论