Alle möglichen Sequenzen A werden von dfs durchsucht, um die maximale Punktzahl zu finden. Zeigen Sie zwei Beispielantworten
--Antwortbeispiel 1 - Implementieren Sie dfs mit rekursiver Funktion --calc Funktion Eine Funktion, die die Punktzahl aus der Sequenz A berechnet
--dfs Funktion Eine Funktion, die die maximale Punktzahl findet, während alle möglichen Sequenzen A mit dfs durchsucht werden. Wenn die Länge der Zahlenfolge A N ist, vergleichen Sie sie nach der Berechnung mit der höchsten Punktzahl und notieren Sie die höchste Punktzahl Wenn die Länge kleiner als diese ist, fügen Sie ein Element hinzu und wiederholen Sie den Vorgang, um die Bedingung der Sequenz A zu erfüllen. Rekursiv durch Hinzufügen von $ x = 1 $, wenn A eine leere Liste ist, andernfalls $ x $ von $ A [-1] \ leqq x \ leqq M $ zu 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()
--Antwortbeispiel 2- itertools.combinations_with_replacement (iterable, r) Durchsuchen Sie die Sequenz A vollständig mit itertools.combinations_with_replacement Gemäß der offiziellen Dokumentation ermöglicht itertools.combinations_with_replacement (iterable, r) aus der Eingabe iterable, dass jedes Element mehrmals angezeigt wird, und gibt einen Teilstring von Elementen der Länge r in einem Taple zurück.
test.py
# itertools.combinations_with_replacement(iterable, r)Anwendungsbeispiel
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
Mit der obigen Funktion kann die Antwort wie folgt geschrieben werden:
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()
Recommended Posts