[PYTHON] Je ne pouvais pas comprendre facilement Fence Repair of Arimoto, donc je vais le suivre en détail.

Se diviser en cas incroyablement simples et réfléchir est un schéma important pour résoudre tout problème. Alors, quel est le cas le plus simple? Réfléchissons ensemble.

Cas de N = 1

Inutile de dire que le cas de $ N = 1 $ est le plus simple. En d'autres termes, la plaque d'origine ne sera pas coupée. Avec cela, il n'y a pas de fluctuation ni de merde, et le coût est toujours de 0 $. Augmentons $ N $.

N = 2 cas

C'est le cas où le nombre de déconnexions est de 1 $. Là encore, il n'y a pas de variation lorsque la longueur de la plaque après découpe est fixée. Augmentons encore $ N $.

N = 3 cas

Désolé de vous avoir fait attendre. Les variations sortent enfin de $ N = 3 $. Tout d'abord, par souci de simplicité, mettons la longueur de la planche après découpe, qui est de 3 $, comme $ A \ leqq B \ leqq C $. Ce serait une hypothèse qui ne perdrait pas sa généralité.

Eh bien, la façon de couper ici est un modèle de 3 $.

• (A+B+C) \rightarrow (A+B),C \rightarrow A,B,C
• (A+B+C) \rightarrow A,(B+C) \rightarrow A,B,C
• (A+B+C) \rightarrow B,(C+A) \rightarrow A,B,C

C'est difficile à comprendre même si je l'écris en lettres, alors j'ai fait un chiffre. Seule la différence dans la partie rouge de la figure affecte le coût total. La position des autres parties est différente, mais la valeur de la somme ne change pas. En d'autres termes, minimiser le coût total dans ce cas équivaut à choisir le plus petit de $ (A + B), (B + C), (C + A) $.

Si vous regardez attentivement pour voir s'il y a suffisamment de variations, choisissez $ 2 $ sur 3 $ $, c'est-à-dire $ {} _3 \ mathrm {C} _2 = {} _3 \ mathrm {C} _1 = 3 $, qui est certainement le modèle $ 3 $. Il ne peut y en avoir. Donc, bien sûr, quel motif est le plus petit est $ (A + B) $, qui est de 2 $ sélectionné à partir de la plus petite valeur.

En résumé, si $ N = 3 $, vous pouvez découper en sélectionnant 2 $ parmi le plus petit. En utilisant ce fait, considérons le cas de $ N = 4 $.

N = 4 cas

Avec $ N = 3 $, nous avons pu affiner le modèle qui minimise le coût total. D'un point de vue méta, puisqu'il s'agit d'une méthode gourmande, il semble qu'il sera possible d'affiner le modèle avec un sentiment progressif après cela.

Maintenant, le cas de $ N = 4 $ a des planches de 4 $. Si vous divisez la caisse dans la première coupe, le motif sera divisé selon que vous coupez la planche $ ABCD $ par 1 $ + 3 $ ou 2 $ + 2 $.

1 + 3 modèles

Le modèle de coupe avec $ 1 + 3 $ est une extension du cas de $ N = 3 $ du côté racine. Après avoir coupé $ 1 $ pour la première fois, il aura la même forme que $ N = 3 $, et la planche $ ABC $ ne changera qu'en $ \ {ABC, ABD, ACD, BCD \} $.

En d'autres termes, il y a un total de 4 $ \ times 3 = 12 $ pattern, mais en réalité cela revient au pattern $ 4 $ dont on coupe en premier. Ici, la généralisation du coût total du cas de $ N = 3 $ est de 2A + 2B + C $. (Choisir le plus petit 2 $ sur 3 $ équivaut à choisir le plus grand)

Par contre, si vous ajoutez $ D $, qui est $ A \ leqq B \ leqq C \ leqq D $, le cas est $ N = 4 $. Le modèle de 4 $ suivant est utilisé pour résumer le coût total.

• $ 3A + 3B + 2C + D $: Coupez d'abord $ D $
• $ 3A + 3B + 2D + C $: Coupez d'abord $ C $
• $ 3A + 3C + 2D + B $: Coupez d'abord $ B $
• $ 3B + 3C + 2D + A $: Coupez d'abord $ A $

Maintenant, arrêtons-nous ici et jetons un coup d'œil au modèle $ 2 + 2 $.

2 + 2 motifs

Si vous y réfléchissez un instant, vous pouvez voir que le coût total sera de 2 $ \ fois (A + B + C + D) $ quelle que soit la combinaison.

Comparez ensemble

En divisant les cas jusqu'à présent, nous avons constaté que les modèles qui doivent être considérés comme le cas de $ N = 4 $ sont réduits à 5 $ au total, y compris le modèle de 4 $ mentionné précédemment.

Maintenant, soustrayons $ 2 \ times (A + B + C + D) $ de tous les cas pour comparer la relation de grandeur de 5 $ $.

• $ ; ; ; ; ; ; 0 ; ; ; ; ; ; $: Première coupée en feuilles $ 2 + 2 $
• $ A + B-D $: Coupez d'abord $ D $
• $ A + B-C $: première coupe $ C $
• $ A + C-B $: Coupez d'abord $ B $
• $ B + C-A $: Coupez d'abord $ A $

Quelle est la valeur qui peut être le coût le plus bas? En considérant $ A \ leqq B \ leqq C \ leqq D $, nous pouvons voir ce qui suit.

• $ ; ; ; ; ; ; 0 ; ; ; ; ; ; $: Minimum si $ A + BD $ est une valeur positive </ strong> POLICE>
• $ A + B-D $: Minimum dans les cas négatifs </ FONT>
• $ A + B-C $: Peut être négatif, mais pas un candidat car le motif jusqu'à $ 1 $ en soustrayant le plus grand nombre $ D $ est plus petit
• $ A + C-B \ geqq 0 $: Pas un candidat car il est toujours $ 0 $ ou plus en raison de la relation de taille
• $ B + C-A \ geqq 0 $: Pas un candidat car il est toujours $ 0 $ ou plus en raison de la relation de taille