问题标题: 酷町堂：7005 买礼物的福利

7005   买礼物的福利

经验值：0 时间限制：1000毫秒

题目描述 Description

酷町猫的小伙伴考上了研究生。酷町猫想买点礼品祝贺她的小伙伴。他带了M元去买礼品，在礼品店里有N种礼品,购买第i种礼品需要 Wi元（若买k个，就需要k*Wi元），现在礼品店在做活动，若他购买第i种礼品，买X(X>0)个的话会获得Ai * X + Bi个糖果。他想得到最多的糖果，请你帮助他计算怎么买奖品可以得到最多的糖果。

输入描述 Input Description

有多个测试用例。 输入的第一行包含一个整数T，表示测试用例的数量。 对于每个测试用例：
第一行包含两个整数 M 和 N。
然后是 N 行，第 i 行包含三个空格分隔的整数 Wi、Ai 和 Bi。

输出描述 Output Description

对于每个测试用例，输出她可以获得的最大糖果。
每组测试样例之间以换行隔开。

样例输入 Sample Input

1 100 2 10 2 1 20 1 1

样例输出 Sample Output

21

数据范围及提示 Data Size & Hint

【样例解释】
酷町猫买了 10 个第一类礼物，并收到 2 × 10 + 1 = 21 个糖果。
【数据范围】
1 ≤ T ≤ 20
1 ≤ M ≤ 2000
1 ≤ N ≤ 1000
0 ≤ Ai, Bi ≤ 2000
1 ≤ Wi ≤ 2000

WA的代码

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
using namespace std;
int T, n, m, v[2005], a[2005], b[2005], w[2005];
int f[200005];
int main() {
//	freopen ("题目名.in", "r", stdin);
//	freopen ("题目名.out", "w", stdout);
	cin >> T;
	while (T --) {
		cin >> m >> n;
		for (int i = 1; i <= n; i ++) {
			cin >> v[i] >> a[i] >> b[i];
		}
		for (int i = 1; i <= n; i ++) {
			for (int j = m; j >= v[i]; j --) {
				f[j] = max(f[j - v[i]] + a[i] + b[i], f[j]);
			}
			for (int j = v[i]; j <= m; j ++) {
				f[j] = max(f[j - v[i]] + a[i], f[j]);
			}
		}
		cout << f[m] << endl;
	}
//	fclose (stdin);
//	fclose (stdout);
	return 0;//好习惯！
}

思路是先拿一个b[i]加一个a[i]，然后再使劲拿a[i]

张恩泽在2021-10-05 11:47:54追加了内容

顶