话说二分答案是个好东西，好打好用～可是对于二分答案解的正确性的验证的方法却有许多。这道题是经典的DP验证，对于这段DP验证可不是那么好想。恩，切入正题。
【题目描述】
一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成m个模块，由公司里的技术人员分工完成。每个技术人员完成同一软件的不同模块的所用的天数是相同的，并且是已知的．但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时 刻只能做一个模块，一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发 期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序．求出公司最早能在什么时候交付 软件。
【输入格式】
输入文件第一行包含两个由空格隔开的整数n和m．其中1≤n≤ 100 ． 1 ≤m≤l00.
接下来的n行每行包含两个用空格隔开的整数d1和d2,d1表示该技术人员完成第一个软件中的一个模块所需的天数，d2表示该技术人员完成第二个软件中的一个模块所需的天数．其中1≤d1，d2 <= 100 。
【输出格式】
输出文件仅有一行包含一个整数d．表示公司最早能于d天后交付软件。
【样例输入】
3 20
1 1
2 4
1 6
【样例输出】
18
【注释】
最快的方案是第一个技术人员完成第二个软件的18个模块．用时18天，第三个技术人员完成第一个软件的18个模块，用时18天．其余的模块由第二个技术人员完成，用时12天，做完所有模块需要18天。如果第一个技术人员完成第二个软件的17个模块．第三个技术人员完成第一个软件的17个模块，其余的模块由第二个技术人员完成．需要用时18天．做完所有模块仍然需要18天，所以少于18天不可能做完所有模块。
又是有关分组的问题，自然而然，可以考虑二分答案。我们用mid来二分最小时间。这样，用F[i,j]表示i个人完成j个第一个项目的模块后还能做的第二个项目的模块总数。只要求出F[n,m]的值，将它和m比较，就知道在mid的时间内，保证做完m个项目一，是不是能做完m个项目二的模块。如果f[n,m]>m，那么mid就是可行解，我们就可以在这个基础上再进行二分，找到最优解。
有了这个思路，动归方程也很明了了。
F[i,j]=max{F[i-1,j-k]+((mid-a[i]*k)div b[i])} (k<=j)
这里k表示只做k个第一个项目的模块，把mid-a[i]*k的时间用来做第二个项目。
注意几点：首先，要注意k<=j这个条件，否则F数组会超界。其次，将F数组初始化成负值是有必要的，因为会出现由于专注于做项目一而不做项目二的情况。这样F[0,0]要初始化成0。另外，二分答案的区间要定够。由于是二分，多定一些关系不大，就是多找几次的事，但是定小了就悲剧了～最后，由于刚开始找出的mid只是可行解，所以如果出现满足f[n,m]>m的情况时应该记录可行解，在[l,mid-1)的区间中继续二分答案。
参考代码：
1 program software;
2 var
3 f: array [ 0 .. 100 , 0 .. 100 ] of integer;
4 i,j,l,r,maxx:integer;
5 n,m,mid,ans,c:integer;
6 a,b: array [ 1 .. 100 ] of integer;
7 function max(x,y:longint):longint;
8 begin
9 if x > y then exit(x)
10 else exit(y);
11 end ;
12 function check(x:longint):longint;
13 var
14 i,j,k:integer;
15 begin
16 for i: = 0 to n do
17 for j: = 0 to m do
18 f[i,j]: =- maxint; // 初始化成负值
19 f[ 0 , 0 ]: = 0 ;
20 for i: = 1 to n do
21 for j: = 0 to m do
22 for k: = 0 to x div a[i] do
23 if k <= j then
24 f[i,j]: = max(f[i,j],f[i - 1 ,j - k] + ((x - a[i] * k) div b[i]));
25 exit(f[n,m]);
26 end ;
27 begin
28 readln(n,m);
29 for i: = 1 to n do
30 begin
31 readln(a[i],b[i]);
32 if a[i] > maxx then maxx: = a[i];
33 if b[i] > maxx then maxx: = b[i]; // 找出最慢的，乘以总模块数为二分上界
34 end ;
35 maxx: = maxx * m;
36 l: = (m * 2 ) div n;
37 r: = maxx;
38 while l <= r do
39 begin
40 mid: = (l + r) div 2 ;
41 c: = check(mid);
42 if c >= m then
43 begin
44 r: = mid - 1 ;
45 ans: = mid;
46 end
47 else l: = mid + 1 ;
48 end ;
49 writeln(ans);
50 end .
（Saltless原创，转载请注明出处）