1000ms

Difficulty: 8

所属公司 : 华为

时间 :2026年1月22日-非AI方向(通软&嵌软&测试&算法&数据科学)

算法标签>

动态规划

解题思路

题目要在以下约束下最大化最终经验值：

初始经验 W、能量 E
每只怪 i：需要经验门槛 X[i]（不消耗经验，只是门槛），打完获得经验 Y[i]，消耗能量 Z[i]
最多打 K 只；若经验/能量不足以打任何怪则提前结束

关键观察：

经验只增不减，所以一组选中的妖怪总能按“门槛 X 从小到大”的顺序去打，越早打门槛低的只会更容易解锁后面的怪。因此先按 X 排序不会损失最优性。
这是一个带“能量约束 + 数量约束”的 0/1 选择问题，但直接做 dp[energy][count] 会炸（E 最大 80000）。
用经典的拉格朗日松弛把“数量约束 K”变成一个可二分的惩罚参数 λ：
- 把每打 1 只怪的收益从 Y 改成 Y - λ
- 对固定 λ，目标变为最大化 sum(Y - λ)，这就能用一维能量 0/1 背包做
- λ 越大，最优解越倾向于少打怪，最优打怪数随 λ 单调不增，因此可以二分 λ

固定 λ 的 DP（按门槛排序后逐个怪做 0/1 背包）：

dpAdj[e]：消耗能量 e 时，最大“调整收益” sum(Y) - λ*cnt
同时记录 dpY[e]（真实经验总收益 sum(Y)）和 dpC[e]（打怪数 cnt）
转移时必须满足可打条件：如果当前真实经验 W + dpY[e] >= X[i]，才能从 e 转到 e+Z[i]

为了保证二分时“打怪数单调”，在比较状态优劣时用以下优先级：

调整收益 dpAdj 大的更好
若 dpAdj 相同，真实收益 dpY 大的更好
若都相同，打怪数 dpC 大的更好（保证单调性）

二分与答案恢复：

先跑 λ=0：若此时最优打怪数已经 ≤K，则 K 不构成限制，直接在所有 cnt<=K 的状态里取真实收益 dpY 最大即可。
否则二分 λ，找到“最大的 λ 使得最优打怪数 ≥ K”。记该 λ 为 lam。
这时原问题（最多 K 只）的最优真实收益满足：
- OPT = bestAdj(lam) + lam*K
再扫描所有能量状态 e，找满足：
- dpC[e] <= K 且 dpAdj[e] + lam*K == OPT
- 在这些状态里取 dpY[e] 最大（并记录对应 dpC），即可得到原问题答案。

最终输出：

最大经验值 = W + bestY
实际打怪个数 = bestC

复杂度分析

设能量上限为 E（≤80000），妖怪数 N（≤1000），λ 二分次数约 log2(1001) ≈ 10：

单次 DP：O(N * E)
总时间：O(N * E * log 1000)
空间：O(E)

代码实现

import sys

def solve(n, w, E, K, X, Y, Z):
    mons = list(zip(X, Y, Z))
    mons.sort(key=lambda t: t[0])  # 按门槛经验排序

    NEG = -10**18

    def run(lam):
        # dpAdj: 最大(sumY - lam*cnt)
        dpAdj = [NEG] * (E + 1)
        dpY = [0] * (E + 1)   # 真实sumY
        dpC = [0] * (E + 1)   # cnt
        dpAdj[0] = 0

        for xi, yi, zi in mons:
            # 0/1背包倒序
            for e in range(E - zi, -1, -1):
                if dpAdj[e] == NEG:
                    continue
                # 经验不足不能打
                if w + dpY[e] < xi:
                    continue

                ne = e + zi
                nadj = dpAdj[e] + yi - lam
                ny = dpY[e] + yi
                nc = dpC[e] + 1

                # 比较：adj优先，其次真实y，再次count(取更大count保证单调性)
                if (nadj > dpAdj[ne] or
                    (nadj == dpAdj[ne] and (ny > dpY[ne] or
                     (ny == dpY[ne] and nc > dpC[ne])))):
                    dpAdj[ne] = nadj
                    dpY[ne] = ny
                    dpC[ne] = nc

        # 取全局最优状态(同样比较规则)
        bestAdj = NEG
        bestY = 0
        bestC = 0
        for e in range(E + 1):
            if dpAdj[e] == NEG:
                continue
            a, yy, cc = dpAdj[e], dpY[e], dpC[e]
            if (a > bestAdj or
                (a == bestAdj and (yy > bestY or
                 (yy == bestY and cc > bestC)))):
                bestAdj, bestY, bestC = a, yy, cc

        return dpAdj, dpY, dpC, bestAdj, bestY, bestC

    # 先试 lam=0：如果最优打怪数 <=K，说明K不紧，直接取最大真实收益
    dpAdj0, dpY0, dpC0, _, _, bestC0 = run(0)
    if bestC0 <= K:
        bestY = 0
        bestC = 0
        for e in range(E + 1):
            if dpAdj0[e] == NEG:
                continue
            if dpC0[e] <= K:
                # 真实收益最大；若相同取打怪数更大（输出更自然且与下方一致）
                if dpY0[e] > bestY or (dpY0[e] == bestY and dpC0[e] > bestC):
                    bestY, bestC = dpY0[e], dpC0[e]
        return w + bestY, bestC

    # 二分：找最大的 lam 使得最优count >= K
    lo, hi = 0, 1001
    while lo < hi:
        mid = (lo + hi + 1) // 2
        _, _, _, _, _, cnt = run(mid)
        if cnt >= K:
            lo = mid
        else:
            hi = mid - 1
    lam = lo

    dpAdj, dpY, dpC, bestAdj, _, _ = run(lam)
    OPT = bestAdj + lam * K  # 原问题最优真实收益

    # 在所有状态中找：cnt<=K 且 adj+lam*K==OPT 的，取真实收益最大
    bestY = 0
    bestC = 0
    for e in range(E + 1):
        if dpAdj[e] == NEG:
            continue
        if dpC[e] <= K and dpAdj[e] + lam * K == OPT:
            if dpY[e] > bestY or (dpY[e] == bestY and dpC[e] > bestC):
                bestY, bestC = dpY[e], dpC[e]

    return w + bestY, bestC

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it)); w = int(next(it)); E = int(next(it)); K = int(next(it))
    X = [int(next(it)) for _ in range(n)]
    Y = [int(next(it)) for _ in range(n)]
    Z = [int(next(it)) for _ in range(n)]
    ans_w, ans_k = solve(n, w, E, K, X, Y, Z)
    print(ans_w, ans_k)

if __name__ == "__main__":
    main()

#include <bits/stdc++.h>
using namespace std;

struct Monster { int x, y, z; };

static inline bool better(int adj1, int y1, int c1, int adj2, int y2, int c2) {
    // adj优先；adj相同，真实y优先；再相同，count大优先(保证二分单调)
    if (adj1 != adj2) return adj1 > adj2;
    if (y1 != y2) return y1 > y2;
    return c1 > c2;
}

struct DPRes {
    vector<int> adj, y, c;
    int bestAdj, bestY, bestC;
};

DPRes runDP(const vector<Monster>& mons, int w, int E, int lam) {
    const int NEG = -1000000000;

    vector<int> dpAdj(E + 1, NEG), dpY(E + 1, 0), dpC(E + 1, 0);
    dpAdj[0] = 0;

    for (auto &m : mons) {
        for (int e = E - m.z; e >= 0; --e) {
            if (dpAdj[e] == NEG) continue;
            // 经验不足不能打
            if (w + dpY[e] < m.x) continue;

            int ne = e + m.z;
            int nadj = dpAdj[e] + m.y - lam;
            int ny = dpY[e] + m.y;
            int nc = dpC[e] + 1;

            if (better(nadj, ny, nc, dpAdj[ne], dpY[ne], dpC[ne])) {
                dpAdj[ne] = nadj;
                dpY[ne] = ny;
                dpC[ne] = nc;
            }
        }
    }

    int bestAdj = NEG, bestY = 0, bestC = 0;
    for (int e = 0; e <= E; ++e) {
        if (dpAdj[e] == NEG) continue;
        if (better(dpAdj[e], dpY[e], dpC[e], bestAdj, bestY, bestC)) {
            bestAdj = dpAdj[e];
            bestY = dpY[e];
            bestC = dpC[e];
        }
    }
    return {dpAdj, dpY, dpC, bestAdj, bestY, bestC};
}

pair<int,int> solve(int n, int w, int E, int K, vector<int>& X, vector<int>& Y, vector<int>& Z) {
    vector<Monster> mons(n);
    for (int i = 0; i < n; i++) mons[i] = {X[i], Y[i], Z[i]};
    sort(mons.begin(), mons.end(), [](const Monster& a, const Monster& b) {
        return a.x < b.x;
    });

    // lam=0 若最优count<=K，K不紧，直接取最大真实收益
    DPRes r0 = runDP(mons, w, E, 0);
    if (r0.bestC <= K) {
        int bestY = 0, bestC = 0;
        for (int e = 0; e <= E; ++e) {
            if (r0.adj[e] == -1000000000) continue;
            if (r0.c[e] <= K) {
                if (r0.y[e] > bestY || (r0.y[e] == bestY && r0.c[e] > bestC)) {
                    bestY = r0.y[e];
                    bestC = r0.c[e];
                }
            }
        }
        return {w + bestY, bestC};
    }

    // 二分：找最大的lam使得最优count >= K
    int lo = 0, hi = 1001;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        DPRes rm = runDP(mons, w, E, mid);
        if (rm.bestC >= K) lo = mid;
        else hi = mid - 1;
    }
    int lam = lo;

    DPRes r = runDP(mons, w, E, lam);
    int OPT = r.bestAdj + lam * K; // 原问题最优真实收益

    // 扫描：cnt<=K 且 adj+lam*K==OPT，取真实收益最大
    int bestY = 0, bestC = 0;
    for (int e = 0; e <= E; ++e) {
        if (r.adj[e] == -1000000000) continue;
        if (r.c[e] <= K && r.adj[e] + lam * K == OPT) {
            if (r.y[e] > bestY || (r.y[e] == bestY && r.c[e] > bestC)) {
                bestY = r.y[e];
                bestC = r.c[e];
            }
        }
    }
    return {w + bestY, bestC};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, w, E, K;
    cin >> n >> w >> E >> K;

    vector<int> X(n), Y(n), Z(n);
    for (int i = 0; i < n; i++) cin >> X[i];
    for (int i = 0; i < n; i++) cin >> Y[i];
    for (int i = 0; i < n; i++) cin >> Z[i];

    auto ans = solve(n, w, E, K, X, Y, Z);
    cout << ans.first << " " << ans.second << "\n";
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {

    static class Monster {
        int x, y, z;
        Monster(int x, int y, int z) { this.x = x; this.y = y; this.z = z; }
    }

    static class DPRes {
        int[] adj, y, c;
        int bestAdj, bestY, bestC;
        DPRes(int[] adj, int[] y, int[] c, int bestAdj, int bestY, int bestC) {
            this.adj = adj; this.y = y; this.c = c;
            this.bestAdj = bestAdj; this.bestY = bestY; this.bestC = bestC;
        }
    }

    static boolean better(int adj1, int y1, int c1, int adj2, int y2, int c2) {
        // adj优先；adj相同，真实y优先；再相同，count大优先(保证二分单调)
        if (adj1 != adj2) return adj1 > adj2;
        if (y1 != y2) return y1 > y2;
        return c1 > c2;
    }

    static DPRes runDP(List<Monster> mons, int w, int E, int lam) {
        final int NEG = -1_000_000_000;

        int[] dpAdj = new int[E + 1];
        int[] dpY = new int[E + 1];
        int[] dpC = new int[E + 1];
        Arrays.fill(dpAdj, NEG);
        dpAdj[0] = 0;

        for (Monster m : mons) {
            for (int e = E - m.z; e >= 0; e--) {
                if (dpAdj[e] == NEG) continue;
                // 经验不足不能打
                if (w + dpY[e] < m.x) continue;

                int ne = e + m.z;
                int nadj = dpAdj[e] + m.y - lam;
                int ny = dpY[e] + m.y;
                int nc = dpC[e] + 1;

                if (better(nadj, ny, nc, dpAdj[ne], dpY[ne], dpC[ne])) {
                    dpAdj[ne] = nadj;
                    dpY[ne] = ny;
                    dpC[ne] = nc;
                }
            }
        }

        int bestAdj = NEG, bestY = 0, bestC = 0;
        for (int e = 0; e <= E; e++) {
            if (dpAdj[e] == NEG) continue;
            if (better(dpAdj[e], dpY[e], dpC[e], bestAdj, bestY, bestC)) {
                bestAdj = dpAdj[e]; bestY = dpY[e]; bestC = dpC[e];
            }
        }
        return new DPRes(dpAdj, dpY, dpC, bestAdj, bestY, bestC);
    }

    static int[] solve(int n, int w, int E, int K, int[] X, int[] Y, int[] Z) {
        List<Monster> mons = new ArrayList<>();
        for (int i = 0; i < n; i++) mons.add(new Monster(X[i], Y[i], Z[i]));
        mons.sort(Comparator.comparingInt(a -> a.x)); // 按门槛排序

        // lam=0 若最优count<=K，K不紧，直接取最大真实收益
        DPRes r0 = runDP(mons, w, E, 0);
        if (r0.bestC <= K) {
            int bestY = 0, bestC = 0;
            for (int e = 0; e <= E; e++) {
                if (r0.adj[e] < -999_999_000) continue; // NEG判断
                if (r0.c[e] <= K) {
                    if (r0.y[e] > bestY || (r0.y[e] == bestY && r0.c[e] > bestC)) {
                        bestY = r0.y[e];
                        bestC = r0.c[e];
                    }
                }
            }
            return new int[]{w + bestY, bestC};
        }

        // 二分：找最大的lam使得最优count >= K
        int lo = 0, hi = 1001;
        while (lo < hi) {
            int mid = (lo + hi + 1) >>> 1;
            DPRes rm = runDP(mons, w, E, mid);
            if (rm.bestC >= K) lo = mid;
            else hi = mid - 1;
        }

        int lam = lo;
        DPRes r = runDP(mons, w, E, lam);
        int OPT = r.bestAdj + lam * K; // 原问题最优真实收益

        // 扫描所有状态：cnt<=K 且 adj+lam*K==OPT，取真实收益最大
        int bestY = 0, bestC = 0;
        for (int e = 0; e <= E; e++) {
            if (r.adj[e] < -999_999_000) continue;
            if (r.c[e] <= K && r.adj[e] + lam * K == OPT) {
                if (r.y[e] > bestY || (r.y[e] == bestY && r.c[e] > bestC)) {
                    bestY = r.y[e];
                    bestC = r.c[e];
                }
            }
        }
        return new int[]{w + bestY, bestC};
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String line;
        while ((line = br.readLine()) != null) sb.append(line).append(' ');
        String s = sb.toString().trim();
        if (s.isEmpty()) return;

        String[] p = s.split("\\s+");
        int idx = 0;

        int n = Integer.parseInt(p[idx++]);
        int w = Integer.parseInt(p[idx++]);
        int E = Integer.parseInt(p[idx++]);
        int K = Integer.parseInt(p[idx++]);

        int[] X = new int[n];
        int[] Y = new int[n];
        int[] Z = new int[n];

        for (int i = 0; i < n; i++) X[i] = Integer.parseInt(p[idx++]);
        for (int i = 0; i < n; i++) Y[i] = Integer.parseInt(p[idx++]);
        for (int i = 0; i < n; i++) Z[i] = Integer.parseInt(p[idx++]);

        int[] ans = solve(n, w, E, K, X, Y, Z);
        System.out.println(ans[0] + " " + ans[1]);
    }
}

题目内容

小明正在玩一款打怪升级游戏灰悟空，游戏中有 $N$ 个妖怪，每个妖怪包含三个正整数属性 ( $X$ $Y$ $Z$ )， $X$ 代表打怪需要的最小经验值（只是打怪需要的经验值门槛，打怪并不消耗经验）， $Y$ 为打怪获得的经验收益， $Z$ 代表打怪消耗的能量。当前悟空的经验值为 $W$ ，能量为 $E$ ，当打死一个妖怪后，他将获得对应的经验值 $Y$ ，并消耗相应的能量 $Z$ 。由于时间有限，小明打算最多打 $K$ 个怪就结束游戏。你能帮他计算游戏结束时悟空的最大经验值和实际打怪个数吗？

备注：

1.当悟空经验或能量不足导致没有可打的妖怪时，游戏自动结束。

2.打死妖怪需要悟空的经验值大于等于打怪需要的最小经验值。

输入描述

第一行： $N$ $N$ $W$ $W$ $E$ $E$ $K$ $K$ ，其中
- $N$ 代表妖怪总数，范围是 $[5,100]$
- $W$ 代表悟空的初始经验值，范围是 $[0,1000]$
- $E$ 代表悟空的初始能量值，范围是 $[0,80000]$
- $K$ 代表小明今天最大打怪个数,范围是 $[1,N-3]$

输出描述

输出 $2$ 个数字，代表游戏结束时悟空的最大经验值和实际打怪个数

样例1

输入

5 0 100 3
0 5 5 8 9
5 3 4 10 6
10 20 30 40 50

输出

19 3

说明

共 $5$ 个妖怪,悟空初始经验为 $0$ ，能量值为 $100$ ，最多打 $3$ 个妖怪，先打唯一满足经验要求的妖怪 $1$ ，获取 $5$ 点经验，消耗 $10$ 点能量，此时悟空经验值为 $5$ ，能量值为 $90$ ，剩余打怪个数 $2$ ，再打经验收益较高的妖怪 $3$ ，获取 $4$ 点经验，消耗 $30$ 点能量，此时悟空经验值为 $9$ ，能量值为 $60$ ，剩余打怪个数 $1$ ，再打经验收益较高的妖怪 $4$ ，获取 $10$ 点经验，消耗 $40$ 点能量，打怪个数用完，游戏结束，此时悟空的经验值为 $19$ ，实际打怪 $3$ 个

样例2

输入

输出

4 2

说明

共 $3$ 个妖怪，悟空初始经验为 $0$ ，能量值为 $100$ ，最多打 $2$ 个妖怪，先打唯一满足经验要求的妖怪 $1$ ，获得 $1$ 点经验，消耗 $5$ 点能量，此时悟空经验值为 $1$ ，能量值为 $95$ ，剩余打怪个数 $1$ ，再打经验收益较高的妖怪 $3$ ，获取 $3$ 点经验，消耗 $20$ 点能量，打怪个数用完，游戏结束，此时悟空的经验值为 $4$ ，实际打怪 $2$ 个

#P4554. 第3题-打怪升级

第3题-打怪升级

解题思路

复杂度分析

代码实现

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About