1022. 宠物小精灵之收服

发布于:2024-08-17 ⋅ 阅读:(93) ⋅ 点赞:(0)

Powered by:NEFU AB-IN

Link

文章目录

题意

思路

https://www.acwing.com/solution/content/117213/

  1. 第一问为二维背包模板
n, V, M = IO.read()
dp = Arr.array2d(0, V + 1, M + 1)

for i in range(n):
    v, m, w = IO.read()
    for j in range(V, v - 1, - 1):
        for k in range(M, m - 1, -1):
            dp[j][k] = Math.min(dp[j][k], dp[j - v][k - m] + w)

print(dp[V][M])
  1. 第二问为求剩余体力最大多少,那就是找二维数组的最后,有多少和f[N][M]相同的数

代码

'''
Author: NEFU AB-IN
Date: 2024-08-15 23:21:56
FilePath: \Acwing\1022\1022.py
LastEditTime: 2024-08-15 23:22:02
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————
import bisect


def dp(N, M, K, balls, blood):
    f = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(K):
        for j in range(N, balls[i] - 1, -1):
            for k in range(M, blood[i], - 1):
                f[j][k] = max(f[j][k], f[j - balls[i]][k - blood[i]] + 1)

    if f[N][M] == 0 : return 0, M

    return f[N][M], M - bisect.bisect_left(f[N], f[N][M]) + 1

N, M, K = map(int, stdin.readline().split())
balls, blood = [0] * K, [0] * K
for i in range(K):
    balls[i], blood[i] = map(int, stdin.readline().split())

C, R = dp(N, M, K, balls, blood)
print(str(C) + ' ' + str(R))


网站公告

今日签到

点亮在社区的每一天
去签到