R Le problème était difficile (je ne pouvais pas analyser la quantité de calcul), et quand je me demandais comment le mettre en œuvre, le temps était écoulé. Peut-être que c'est correct de le faire passer, alors ce serait peut-être une bonne idée de le lancer. En conséquence, NoSub a été retiré ... Aussi, j'aimerais résoudre le problème B pendant mon temps libre cette semaine.
Tout d'abord, je voudrais mentionner les méthodes envisagées lors du concours. Je pensais que +1 et -1 étaient pour l'ajustement, et je pensais qu'il pourrait être uniquement déterminé en ** répétant n'importe lequel de 2x, 3x et 5x. Par conséquent, je pensais que $ n $ devrait être considéré comme un numéro de base $ k $ ($ \ in $ {$ 2,3,5 $}), mais bien sûr, cela n'est pas décidé en se référant à l'échantillon (1 sans le remarquer) Il a fondu pendant plus d'une heure. Si vous vous précipitez, vous ne pourrez pas penser logiquement ...).
D'ailleurs, avant de m'en tenir à cette politique, j'ai essayé de penser à DP ** qui a noté le nombre de pièces requises de ** $ n $ à 0, et j'ai décidé que c'était impossible car le nombre d'éléments DP est de $ n $. C'était. ** Vous pouvez accélérer DP en utilisant un dictionnaire au lieu d'un tableau **, vous pouvez donc le résoudre par cette méthode (proche de) que vous avez trouvée ...
Maintenant, envisagez d'utiliser $ n $ pour +1, -1, ÷ 2, ÷ 3, ÷ 5 pour le rendre 0. Premièrement, lorsque vous connaissez le nombre de pièces dont vous avez besoin pour un certain $ l $, utilisez +1, -1, ÷ 2, ÷ 3, ÷ 5 pour réduire le nombre de destinations ** (** état) Limited ** est la base comme DP) Par exemple, supposons que vous vouliez faire $ l $ ÷ 5. Puisque $ l $% 5 = 0 est requis pour que cette réponse soit un entier, laissez $ l $ agir +1, -1 pour la rendre divisible par 5.
Ici, si vous appliquez +6 ou plus ou -6 ou moins à $ l $, vous utiliserez des pièces de 6 $ \ fois D $ ou plus à ce stade, mais dans ce cas, ** 6 ou plus ou -6 ou moins. Il est clair qu'il est plus efficace de le casser avant de le casser après l'avoir laissé fonctionner **. 11 → 10 → 1 ("-1" × 1 → "÷ 5" → "-1" × 1) est meilleur que (par exemple 11 → 5 → 1 ("-1" × 6 → "÷ 5")) Vous dépenserez moins de pièces.) (Vous pouvez probablement le prouver en faisant quelque chose de similaire, mais je vais l'omettre ici.)
De même, si le nombre de pièces nécessaires pour faire un certain l et le nombre à diviser $ k $ ($ \ in $ {$ 2,3,5 $}) sont déterminés, le nombre minimum de pièces sera obtenu. Dans une telle opération, déplacez-vous vers un multiple du nombre que vous souhaitez diviser (2,3,5) proche de ** $ l $ ** (← Notez qu'il y en a deux, il s'écrit * le plus proche * dans le code) Puis divisez et effectuez le calcul suivant. À ce moment, une structure récursive (structure fractale) apparaît, vous pouvez donc implémenter la récurrence, et vous pouvez implémenter le mémorial DFS (également considéré comme DP).
Notez également que dans certains cas, il est préférable de faire simplement -1 et de passer de $ l $ à $ 0 $ sans utiliser la division. (← Jusqu'à présent, si vous voulez viser 0 avec ** ÷ 2, ÷ 3, ÷ 5, vous ne pensez qu'à **, donc si vous voulez viser 0 avec ** -1, vous devez considérer ** Bien sûr.)
A.py
def dfs(n):
global b,check,d
#ttf est 235, cha est abc
#2,3,Dans le cas de 5, chacun
for ttf,cha in zip([2,3,5],b):
#-En allant un par un
if check[0]>check[n]+n*d:
check[0]=check[n]+n*d
#Au plus proche-Si tu fais
x1,x2=n//ttf,n%ttf
if x1 in check:
if check[x1]>check[n]+x2*d+cha:
check[x1]=check[n]+x2*d+cha
dfs(x1)
else:
check[x1]=check[n]+x2*d+cha
dfs(x1)
#Au plus proche+Quand 1
x1,x2=n//ttf+1,ttf-n%ttf
if x1 in check:
if check[x1]>check[n]+x2*d+cha:
check[x1]=check[n]+x2*d+cha
dfs(x1)
else:
check[x1]=check[n]+x2*d+cha
dfs(x1)
t=int(input())
for i in range(t):
N,*b,d=map(int,input().split())
check={N:0,0:N*d}
dfs(N)
print(check[0])
Recommended Posts