1022. 宠物小精灵之收服
Powered by:NEFU AB-IN
Link
文章目录 题意思路代码题意
略
思路
https://www.acwing.com/solution/content/117213/
第一问为二维背包模板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]) 12345678910 第二问为求剩余体力最大多少,那就是找二维数组的最后,有多少和f[N][M]相同的数
代码
''' Author: NEFU AB-IN Date: 2024-08-15 23:21:56 FilePath: Acwing10221022.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("rn")) 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))
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273相关知识
宠物小精灵之收服
宠物小精灵之收服(二维背包)
1292:宠物小精灵之收服
【动态规划】宠物小精灵之收服
信息学奥赛一本通 1292:宠物小精灵之收服 动态规划
[编程题]四、宠物小精灵之收服 描述 宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。 一天,小智和皮卡丘来到了小精灵狩猎场,里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而,野生的小
宠物小精灵之冠军皮卡丘
《宠物小精灵》的全集目录
宠物小精灵之冠军之上
宠物小精灵之极限培养
网址: 1022. 宠物小精灵之收服 https://www.mcbbbk.com/newsview581251.html
上一篇: mysql第十章宠物商店 宠物商 |
下一篇: 搜宠网,一个搭建你与它相遇的桥梁 |
推荐分享

- 1我的狗老公李淑敏33——如何 5096
- 2南京宠物粮食薄荷饼宠物食品包 4363
- 3家养水獭多少钱一只正常 3825
- 4豆柴犬为什么不建议养?可爱的 3668
- 5自制狗狗辅食:棉花面纱犬的美 3615
- 6狗交配为什么会锁住?从狗狗生 3601
- 7广州哪里卖宠物猫狗的选择性多 3535
- 8湖南隆飞尔动物药业有限公司宠 3477
- 9黄金蟒的价格 3396
- 10益和 MATCHWELL 狗 3352