Codeforces 189A:Cut Ribbon(完全背包,DP)
发布日期:2022-04-01 13:25:18 浏览次数:42 分类:博客文章

本文共 2623 字,大约阅读时间需要 8 分钟。

time limit per test : 1 second

memory limit per test : 256 megabytes

input : standard input

output : standard output

Polycarpus has a ribbon, its length is

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
    ,
    b
    b
    or
    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.

Input

The first line contains four space-separated integers

n
n
,
a
a
,
b
b
and
c
c
(
1
n
,
a
,
b
,
c
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
,
b
b
and
c
c
can coincide.

Output

Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.

Examples

input

5 5 3 2

output

2

input

7 5 5 2

output

2

Note

In the first example Polycarpus can cut the ribbon in such way: the first piece has length

2
2
, the second piece has length
3
3
.

In the second example Polycarpus can cut the ribbon in such way: the first piece has length

5
5
, the second piece has length
2
2
.

Solve

完全背包,看成给出三种商品,恰好能够装满背包的情况

注意初始化的问题,如果把

d
p
dp
数组全部初始化为
1
-1
的话,需要注意
d
p
[
j
]
=
1
&
&
d
p
[
j
a
[
i
]
]
=
1
dp[j]=-1\&\&dp[j-a[i]]=-1
的情况。或者就全部初始值给成小于
1
-1
的数

Code

/*************************************************************************	 > Author: WZY	 > School: HPU	 > Created Time:   2019-04-01 18:30:38	 ************************************************************************/#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long#define ull unsigned long long#define lson o<<1#define rson o<<1|1#define ms(a,b) memset(a,b,sizeof(a))#define SE(N) setprecision(N)#define PSE(N) fixed<
x) x=y;}inline void MIN(ll &x,ll y) {if(y
x) x=y;}template
void Debug(FIRST arg, REST... rest){ cerr<
<<"";Debug(rest...);}int dp[maxn];int main(int argc, char const *argv[]){ ios::sync_with_stdio(false);cin.tie(0); cout.precision(20); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); srand((unsigned int)time(NULL)); #endif int n; int a[4]; cin>>n>>a[0]>>a[1]>>a[2]; ms(dp,-1); dp[0]=0; for(int i=0;i<3;i++) for(int j=a[i];j<=n;j++) if(dp[j-a[i]]!=-1) MAX(dp[j],dp[j-a[i]]+1); cout<
<

转载地址:https://www.cnblogs.com/Friends-A/p/11054959.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:ZOJ 3872: Beauty of Array(思维)
下一篇:第九届河南理工大学算法程序设计大赛 正式赛L:最优规划(最小生成树)

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月01日 01时04分20秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux线程存储,Linux系统编程手册:线程:线程安全和每线程存储 2019-04-21
c语言编程max,C语言编程题及答案.doc 2019-04-21
android测试页面,自动执行界面测试 | Android 开发者 | Android Developers 2019-04-21
android 图片点击变色,Android开发实现ListView点击item改变颜色功能示例 2019-04-21
电脑端的mafsvr服务关掉_网吧才是电脑优化的精髓!学会3招你也不用羡慕网吧的流畅了... 2019-04-21
html获取文件路径_HTML 文件路径 2019-04-21
mysql滴的一声就关了_关于mysql数据库在输入密码后,滴的一声直接退出界面的解决办法(详细办法)... 2019-04-21
mysql in 有序_mysql中的in排序 mysql按in中顺序来排序 2019-04-21
mysql 行转列 显示_mysql 行转列 (结果集以坐标显示) 2019-04-21
由于连接方在一段时间后没有正确答复或连接的主机_新风换气机使用效果不佳,为何?掌握正确使用方法就好了... 2019-04-21
mysql 查询姓王_MySQL查询语句练习题,测试足够用了 2019-04-21
mysql多实例脚本_mysql多实例脚本 2019-04-21
python如何生成excel文件夹_用python脚本通过excel生成文件夹树结构 2019-04-21
python获取post请求中的所有参数_Django从POST reques获取请求参数 2019-04-21
mysql加密复制_MySQL主从复制使用SSL加密 2019-04-21
python启动远端 exe_python打包exe开机自动启动的实例(windows) 2019-04-21
java当前路径_java获取当前路径的几种方法 2019-04-21
java web传递参数_Javaweb的八种传值方式 2019-04-21
java gui支持的包有哪两个_Java GUI 2019-04-21
java list详解_java集合List解析 2019-04-21