题目名称	1078. [NOIP 2010冲刺六]软件开发
输入输出	`time.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	11
题目来源	sywgz 于2012-09-25加入
开放分组	全部用户
提交状态
分类标签	分治搜索法动态规划类背包
	分享题解

通过：132，提交：259，通过率：50.97%
瑆の時間~無盡輪迴·林蔭	100	0.000 s	0.00 MiB	C++
_Itachi	100	0.004 s	0.29 MiB	C++
AAAAAAAAAA	100	0.007 s	0.31 MiB	C++
L_in	100	0.010 s	0.36 MiB	C++
苏轼	100	0.011 s	0.21 MiB	Pascal
stdafx.h	100	0.011 s	0.34 MiB	C++
苏轼	100	0.012 s	0.21 MiB	Pascal
deadpool66	100	0.012 s	0.32 MiB	C++
槿柒	100	0.014 s	0.13 MiB	C++
liucxy	100	0.017 s	0.29 MiB	C++

本题关联比赛
20120925
2016-10-11 4 syz

关于软件开发的近10条评论(全部评论)
hack 一发边界数据 Arrow 2017-09-07 17:51 11楼
AntiLeaf 2017-05-25 16:03 10楼
我真是作啊，，，，，， Tabing010102 2016-10-21 15:23 9楼
榜一的表很专业啊森林 2016-08-03 19:49 8楼
考试时写的二分答案+显然错误的贪心，居然过了5个点 _Itachi 2016-08-03 16:43 7楼
血的教训告诉循环从0开始半汪 2016-08-03 14:06 6楼
我在这 0 2015-08-12 15:29 5楼
ZGY大神曾云:背包这个东西,是各大比赛最爱考的; 把基础书上的背包[P283]再好好看一遍吧,说不定又会有新的收获. <蒟蒻>我要喝豆奶 2015-08-12 15:27 4楼
二维费用+多重背包。。。。全T了试试DQ优化 <蒟蒻>我要喝豆奶 2015-08-12 15:27 3楼
因为没判第一个人的时间是否超了上限，调了半天。天一阁 2014-09-22 13:28 2楼

1078. [NOIP 2010冲刺六]软件开发

★★ 输入文件：time.in 输出文件：time.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成m个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的所用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序，求出公司最早能在什么时候交付软件。

【输入格式】

输入文件第一行包含两个由空格隔开的整数n和m，其中1≤n≤100,1≤m≤100。接下来的n行每行包括两个用空格隔开的整数d1和d2，d1表示该技术人员完成第一个软件中的一个模块所需的天数，d2表示该技术人员完成第二个软件中的一个模块所需的天数，其中1≤d1，d2≤100。

【输出格式】

输出文件仅有一行包含一个整数d，表示公司最早能于d天后交付软件。

【样例输入】

3 20

1 1

2 4

1 6

【样例输出】

样例的最快方案是第一个技术人员完成第二个软件的18个模块，用时18天，第三个技术人员完成第一个软件的18个模块，用时18天，其余的模块由第二个技术人员完成，用时12天，做完所有模块需要18天。如果第一个技术人员完成第二个软件的17个模块，第三个技术人员完成第一个软件的17个模块，其余的模块由第二个技术人员完成，需要用时18天，做完所有模块仍然需要18天，所以少于18天不可能做完所有模块。

【提示】

20%的数据1≤n,m≤10
40%的数据1≤n,m≤20

100%的数据1≤n,m,d1,d2≤100

【来源】

在此键入。