rqnoj 160 竞赛真理 分组背包

缘起

学习分组背包~ rqnoj 160 竞赛真理

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
题目描述

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

输入格式
第一行有两个正整数N和T，表示题目的总数以及　竞赛的时限（单位秒）。以下的N行，每行４个正整数
W1i 、T1i 、W2i 、T2i ，

分别表示第i题：完全正确做出来的得分，完全正确做出来所花费的时间（单位秒），“骗”来的分数，“骗”分所花费
的时间（单位秒）。其中，3 ≤N ≤30，2 ≤T ≤ 1080000，1 ≤ W1i 、W2i ≤ 30000，1 ≤ T1i 、T2i ≤ T。

输出格式
直接把所能得到的最高分值输出

样例输入
4 10800
18 3600 3 1800
22 4000 12 3000
28 6000 0 3000
32 8000 24 6000

样例输出
50

分组背包裸题~ 物品如下

第1题ac，第1题骗分，第1题不做.

第2题ac，第2题骗分

… …

第n-1题ac，第n-1题骗分

第n题ac，第n题骗分

即2n个物品, 每2个物品在一个物品组中互斥. 容量为T. 跑分组背包模板即可

ps: 为什么没有第i题不做? 因为这其实是不选这个物品组中任何一个物品这种方式. 所以没必要放进物品组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//#include "stdafx.h"
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 35, maxv = 1080005;
int n,t, w1[maxn], t1[maxn], w2[maxn], t2[maxn],dp[maxv];

void read(int &x)
{
    x = 0;
	int f = 1;
	char c = getchar();
	while(!isdigit(c))
	{
		if (c=='-')
		{
			f = -1;
		}
		c = getchar();
	}
	while(isdigit(c))
	{
		x = (x<<3)+(x<<1)+(c^48);
		c = getchar();
	}
	x*=f;
}

void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x = -x;
	}
	if (x>9)
	{
		write(x/10);
	}
	putchar(48+x%10);
}

void gp()
{
	for (int k = 1;k<=n;k++)
	{
		for (int v = t; ~v; v--)
		{
			if (v>=t1[k])
			{
				dp[v] = max(dp[v], dp[v-t1[k]]+w1[k]);
			}
			if (v>=t2[k])
			{
				dp[v] = max(dp[v], dp[v-t2[k]]+w2[k]);
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\data.in", "r", stdin);
//	freopen("d:\my.out", "w", stdout);
#endif
	read(n), read(t);
	for (int i = 1;i<=n;i++)
	{
		read(w1[i]),read(t1[i]),read(w2[i]),read(t2[i]);
	}
	gp();
	write(dp[t]);
	return 0;
}

ac情况

1
1241183160竞赛真理yfsAC 1002019-10-25 21:36