Codevs 1371 浴火银河跑运输

时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold

题目描述 Description：

小 K 又在玩浴火银河了。。。不过这次他的目的真的是跑运输赚钱。。。

他想知道在两个星系之间跑运输最多可以赚多少钱。

他的路线是【星系 1—星际 2】

输入描述 Input Description：

第一行，两个数，A,B；

A 代表有多少种货物；B 代表小 K 的飞船最大承载重力；

接下来的 A 行：第 i 行表示第 i 种货物的信息：

{在星系 1 的价格}{在星系 2 的价格}{在星系 1 货物的件数}{每件货

物的重力}

输出描述 Output Description：

仅一行，运输的最大盈利。

货物的重力总和不能超过 B。

样例输入 Sample Input：

3 9

13 63 1 8

2 5 4 9

7 16 9 6

样例输出 Sample Output：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int n,m;
 6 int w[110],f[110],c[110],v[110];
 7 int main()
 8 {
 9     cin>>m>>n;
10     for(int i=1;i<=n;i++)
11     {
12         int x,y;
13         cin>>x>>y;
14         cin>>c[i];
15         cin>>w[i];
16         v[i]=y-x;
17     }
18     memset(f,0,sizeof f );
19     for(int i=1;i<=n;i++)
20       for(int k=1;k<=c[i];k++)
21         for(int j=m;j>=w[i];j--)
22           f[j]=max(f[j],f[j-w[i]]+v[i]);
23     
24     printf("%d",f[m]);
25     return 0;
26 }