Toutes les séquences possibles A sont recherchées par dfs pour trouver le score maximum. Afficher deux exemples de réponses
Fonction --dfs Une fonction qui trouve le score maximum lors de la recherche de toutes les séquences A possibles avec dfs. Si la longueur de la séquence de nombres A est N, après avoir calculé le score, comparez-le avec le score le plus élevé à ce jour et enregistrez le score le plus élevé Si la longueur est inférieure à cela, ajoutez un élément et se répète de manière à satisfaire la contrainte de la séquence A. Récursif en ajoutant $ x = 1 $ si A est une liste vide, sinon $ x $ de $ A [-1] \ leqq x \ leqq M $ à A
main.py
#!/usr/bin/env python3
def main():
import sys
def calc(A: list):
score = 0
for a, b, c, d in lst:
if A[b - 1] - A[a - 1] == c:
score += d
return score
def dfs(A: list):
nonlocal ans
if len(A) == N:
ans = max(ans, calc(A))
return
for v in range(A[-1] if A else 1, M + 1):
A.append(v)
dfs(A)
A.pop()
input = sys.stdin.readline
N, M, Q = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
dfs([])
print(ans)
main()
--Exemple de réponse 2- itertools.combinations_with_replacement (iterable, r) Recherchez complètement la séquence A en utilisant itertools.combinations_with_replacement Selon la documentation officielle, itertools.combinations_with_replacement (iterable, r) tapule une sous-chaîne d'éléments de longueur r à partir de l'entrée itérable, permettant à chaque élément d'apparaître plusieurs fois.
test.py
# itertools.combinations_with_replacement(iterable, r)Exemple d'utilisation
from itertools import combinations_with_replacement
for pattern in combinations_with_replacement('ABCD', 2):
print(pattern, end='')
# AA AB AC AD BB BC BD CC CD DD
En utilisant la fonction ci-dessus, la réponse peut être écrite comme suit:
main.py
#!/usr/bin/env python3
def main():
import sys
from itertools import combinations_with_replacement
input = sys.stdin.readline
N, M, Q = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
for pattern in combinations_with_replacement(range(1, M + 1), N):
res = 0
pattern = list(pattern)
for a, b, c, d in lst:
if pattern[b - 1] - pattern[a - 1] == c:
res += d
ans = max(ans, res)
print(ans)
main()
--Atto TECH LOG
ABC165 C - Many Requirements
https://at274.hatenablog.com/entry/2020/05/20/213705
Recommended Posts