2025/5/17 模拟赛 T4 题解

chrisgr · 2025-05-17 16:38:40 · 个人记录

题解

题面描述

有 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

#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;
}