2017.08.15【NOIP提高组】模拟赛B组 生日聚餐

####Description

Alice在餐馆里当服务员，今天是她生日，她请求厨师帮她准备生日晚餐，晚餐由N种原料做成，每道菜所需每种原料的数量是一样的。
　　厨房里有一些原料，但不够，Alice还需要从旁边的超市中购买一些回来。超市里什么原料都有，每种原料都分大包装和小包装。Alice有M元钱，她想利用这M元钱购买原料使得能做出最多的菜。

####Input

第一行包含两个整数N和M(1<=N<=100,1<=M<=100000)，接下来N行，每行包含6个正整数，用来描述这种原料的信息，具体如下：
　　(1) X：10<=X<=100，表示一道菜中必须含有这种原料的数量；
　　(2) Y：1<=Y<=100，表示这种原料厨房已有的数量；
　　(3) Sm：1<=Sm<=100，表示超市里小包装中含有这种原料数量；
　　(4) Pm：10<=Pm<=100，表示小包装的价格；
　　(5) Sv：1<=Sv<=100，表示超市里大包装中含有这种原料数量； 　　
(6) Pv：10<=Pv<=100，表示大包装的价格；

####Output

输出最多能做多少道菜。

####Sample Input

输入1：
2 100
10 8 10 10 13 11
12 20 6 10 17 24

输入2：
3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16

####Sample Output

输出1：
5

输出2：
2

####Data Constraint

样例1中，Alice购买第一种原料3个小包装和1个大包装，购买第二种原料1个小包装和2个大包装，一共花费3×10+1×11+1×10+2×24=99元。
　　两种原料的数量分别为51个（8+3×10+11）和60个（20+1×6+2×17），可以做出5道菜。

题解：
可以先求完全背包，然后枚举答案，二分答案也是可以的。　　
这里介绍完全背包。
我们用f[i,j]表示第i种材料，用j数量的最小价值
我们就直接用完全背包找出来即可。
但是我们又发现一个问题：假如你需要用5个，但是只可以用2块钱买3个，那么是需要买6个用4块的，那么久更新一下。
最后我们枚举答案(也就是从大到小枚举可以做多少道菜)，若是你想用二分，也可以。
但是f数组的空间会炸，所以可以使用动态数组。
这是个新的东东，大家可以看看。
　　下面是一维的定义方式（pascal），二维的只需要加多括号内容

　　var

　　　　a:array of (array of) longint;

　　begin

　　　　setlength(a,s,(s1))//表示第一维下标开0~s-1大小，括号中，第二维表示下标开从0~s1-1大小

　　end.

但是根据题意，我们怎么定义呢？？
只需要定义f[n,(m10) div n +100]即可，这是为什么呢？
我们想：若是根据题意来开到100100000当然会炸。上式即可解决。
我们看看为什么这样搞：
因为最多是10块钱买100个，也就是1块钱买10个，然后买下来的所有东东平均分成n份，那么每份最多就只可以用(m*10) div n，而且一开始厨房内最多有100个原料，那么就+100即可。

Code

uses math;
var
        i,j,k,l,n,m,ans,small,answer,zd:longint;
        s:ansistring;
        bz:boolean;
        a,b,sm,pm,sv,pv:array[1..100] of longint;
        f:array of array of int64;
function min(x,y:int64):int64;
begin
        if x>y then exit(y)
        else exit(x);
end;
begin
        readln(n,m);
        i:=n+1;
        j:=(m*10) div n+101;
        setlength(f,i,j);
        for i:=0 to n do
        begin
                for j:=0 to (m*10) div n+100 do
                begin
                        f[i,j]:=maxlongint;
                end;
        end;
        for i:=1 to n do
        begin
                readln(a[i],b[i],sm[i],pm[i],sv[i],pv[i]);
                zd:=max(a[i],zd);
                for j:=1 to b[i] do
                f[i,j]:=0;
        end;
        j:=1;
        for i:=1 to n do
        begin
                for j:=sm[i] to (m*10) div n+100 do
                begin
                        f[i,j]:=min(f[i,j],f[i,j-sm[i]]+pm[i]);
                end;
                for j:=sv[i] to (m*10) div n+100 do
                begin
                        f[i,j]:=min(f[i,j],f[i,j-sv[i]]+pv[i]);
                end;
        end;
        for i:=1 to n do
        begin
                for j:=(m*10) div n+100-1 downto 0 do
                begin
                        f[i,j]:=min(f[i,j],f[i,j+1]);
                end;
        end;
        for i:=((m*10) div n+100) div zd downto 1 do
        begin
                if i=46685 then
                ans:=0;
                ans:=0;
                bz:=true;
                for j:=1 to n do
                begin
                        if ans+f[j,i*a[j]]<=m then
                        begin
                                ans:=ans+f[j,i*a[j]];
                        end
                        else
                        begin
                                bz:=false;
                                break;
                        end;
                end;
                if bz then
                begin
                        writeln(i);
                        halt;
                end;
        end;
        writeln(0);
end.