本文共 1622 字，大约阅读时间需要 5 分钟。

竞赛真理

Time Limit:1000MS Memory Limit:65536K

Total Submit:569 Accepted:213

Description

TENSHI在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是要完全正确地做对一题是要花很多时间（包括调试时间），而竞赛的时间有限。所以开始做题之前最好先认真审题，估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。 当然，如果做完了预先选择的题目之后还有时间，但是这些时间又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一点分数。

任　务　：根据每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，哪些题目 　　　　　“骗”分，哪些不做），使能在限定的时间内获得最高的得分，

Input

第一行有两个正整数N和T，表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行４个正整数W1i 、T1i 、W2i 、T2i ，分别表示第i题：完全正确做出来的得分，完全正确做出来所花费的时间（单位秒），“骗”来的分数，“骗”分所花费的时间（单位秒）。

其中，3 ≤ N ≤ 30，2 ≤ T ≤ 1080000，1 ≤ W1i 、W2i ≤ 30000，1 ≤ T1i 、T2i ≤ T。

Output

所能得到的最高分值

Sample Input

样例1

4 10800

18 3600 3 1800 22 4000 12 3000 28 6000 0 3000 32 8000 24 6000

样例2

3 7200

50 5400 10 900 50 7200 10 900 50 5400 10 900 Sample Output

样例1

50

样例2

70

思路

这题完全可以用做，每组有完全正确和“骗”分😊两种选择容量则为时限。

状态转移方程： $1<=i<=n,v>=k>=1,a=f[k]$ $k>=c[i],a=max(a,f[k-c[i]]+w[i])$ $k>=cc[i],a=max(a,f[k-cc[i]]+ww[i])$ $f[k]=a$ 详解请点击

代码

#include
   
    using namespace std;int v,n,w[31],c[31],p,a,f[1080001],ww[31],cc[31];void in(){
   	scanf("%d%d",&n,&v);	for(int i=1;i<=n;i++){
   		scanf("%d%d%d%d",&w[i],&c[i],&ww[i],&cc[i]);	}}void dp(){
   	for(int i=1;i<=n;i++){
   		for(int k=v;k>=1;k--){
   			a=f[k];			if(k>=c[i]) a=max(a,f[k-c[i]]+w[i]);			if(k>=cc[i]) a=max(a,f[k-cc[i]]+ww[i]);			//选出正解和骗分最大的价值			f[k]=a;		}	} 	}int main(){
   	in();	dp();	cout<