题解

题面描述

有

n

种物体，每种物体有

a

和

b

两个属性，数量无穷多，且物体单价只与

\frac{b}{a}

有关，若

\frac{b}{a}

不降，则物体单价不降，且物体间可无限合并，问

a

不大于

m

时物体的总价最大为多少。

sol

若随意合并，则合并后可产生的物体过多，无法处理。所以我们需要想办法让可更新答案的物体在一个可以接受的范围内。不难发现只有

m \ge a

的物体可以更新答案，且所有物体均有无穷多个，所以我们可以记录不同

a

时最大的价值是多少，以此更新答案，因为价值关于

b

存在单调性，所以记录最大的价值可通过记录

b

实现，这个东西很容易通过完全背包求出，时间复杂度

O(m^2)

。最后对这

m

种物体做完全背包即可，时间复杂度

O(m^2)

。

CODE

CPP

#include<bits/stdc++.h>
using namespace std;
int n, m, v[10], val[3005], ans[3005];
int main() {
//	freopen("stone.in", "r", stdin);
//	freopen("stone.out", "w", stdout);
	int t;
	scanf("%d", &t);
	while(t--) {
		memset(val, -0x3f, sizeof(val)), memset(ans, 0, sizeof(ans));
		for(int i = 0; i < 10; ++i) scanf("%d", v + i);
		scanf("%d%d", &n, &m);
		for(int i = n; i; --i) {
			int a, b;
			scanf("%d%d", &a, &b);
			val[a] = max(val[a], b);
		}
		for(int i = 1; i <= m; ++i) 
			for(int j = 1; i + j <= m && j <= i; ++j) 
				val[i + j] = max(val[i + j], val[i] + val[j]);
		for(int i = m; i; --i) {
			if(val[i] > 0) {
				int now = (val[i] * 10 - 1) / i;
				for(int j = 0; j + i <= m; ++j) ans[i + j] = max(ans[i + j], ans[j] + i * v[now]);
			}
		}
		printf("%d\n", ans[m]);
	}
	return 0;
}

2025/5/17 模拟赛 T4 题解

文章操作

题解

题面描述

sol

CODE

相关推荐

评论

2025/5/17 模拟赛 T4 题解