La communication des acacias⚓︎

Mécanisme de synchronicité

Une des observations les plus anciennes a été faite sur les girafes par Wouter Van Hoven. Il a étudié pendant 2 ans le comportement des girafes dans un parc national en Afrique du Sud. Les girafes ingurgitent environ 80 kg de feuilles par jour. Pourtant, lorsqu'elles arrivent sur un acacia, elles ne restent que quelques minutes, broutent que quelques feuilles puis vont vers un autre arbre. L'arbre a réagi à la présence de la girafe en secrétant des tanins. Ce sont des molécules amères et toxiques pour les girafes. Mais en même temps, l'acacia va émettre de l'éthylène, qui est un gaz qui va se déplacer dans l'air et informer les autres arbres qu'un prédateur est là. Que vont faire les autres arbres ? Ils vont augmenter de manière préventive leur teneur en tanin et se préparer à l'arrivée des girafes.

On vous donne une liste de quantités de feuilles que pourrait manger une girafe sur un arbre à un indice donné le long d'une ligne d'acacias. La seule contrainte, c'est que la girafe ne peut pas manger les feuilles sur deux arbres consécutifs, mais souhaite en manger le plus possible. Écrire une fonction qui indique quelle quantité totale la girafe peut ingurgiter.

Exemples

🐍 Console Python

>>> feuilles = [4, 25, 20, 8, 17]
>>> max_manger(feuilles)
42

La girafe peut manger $25+17 = 42$ feuilles au maximum.

Prendre $4+20+17$ n'en donne que $41$.

🐍 Console Python

>>> feuilles = [4, 6, 5, 7, 4]
>>> max_manger(feuilles)
13

La girafe peut manger $4+5+4=13$ ou bien $6+7=13$ feuilles au maximum.

Nombre d'opérations limité

Votre solution doit pouvoir être efficace même avec de grands tableaux. Il est demandé d'utiliser une programmation dynamique. Dans le cas contraire, votre solution ne passera probablement pas les tests cachés.

Compléter le code suivant

Évaluations restantes : 5/5

.128013[(lbsS]etxph4rd5f1890uma"ov+w7g,_/3=in 6k:)y 2Pc030j0c0d0s0F07090N0Q070s09090E0t0d0F0f0t020H03090q0r0r0s0i0M020a0u070q0*0u0G030C0;0?0^0`0/0f02031a131d0C1a0/0j0F0v0Z0#0%0(0g0F0z0g071r0g0d0-030U08070c1m0$0'0t1q1s1u1s0d1A1C1y0d0i1b0d0g0Z0}090f0s0G0(0O0t1E1o0t0l0W0c0G0s0r0c1y1X1Z1'1G1*1C1-1/0-040N0P0i0u0f0u090F100G0N0S1V0i0i0c0Q27131=0G1b0C1T2k1Q1S1R1z0j1@0(1u0G1,241y1j1l0!1F2u0F2w0G0u2A1y0f2d1b2i2k2O0:1Y282C1(2H0i0@070-0N0m2h2S0.2R1?2U1G2W2Y2!0O2%1Z2(2i2t0t2-0s2Z020N0D2;2j0/2@2+0(2`2|0N0h302?2S2^362!0k3a323c342_0u2X2{2!0I3h2)2T1n2,3m2.2}0y3r333u353w3o2}0n3A3j3C3l3n370o3I2*3K3e020m0p3P3t2D3L3x0m2$142'1e2M132A2n0j1S2s3k0Q2I1:1b3+1c3)2Q3%2=033;0S2N3J3Y0J0-0S0l3a0N3s3d0l0-0@0e0B0@0G0z0c0i3a4a3k0,02064m3B3Y0G0-0l0c0q0W1C094s421(4p0L0K3h0N4K494t2V0-123|2j4M4E1G0u0-0E484n3R080-1`4D3Q3Y4p4r4R414)4O024x4z074B4(3X4F0-0L4J4L4!430-0F474-4T4/2,4P4Z4N4V4X4Y55501(0r0F0-3V4-5g1G4p4I4-0H4L5t564`1G44022d0d0q0i4Q2O5v2^5i5k4~4K5n354d0s0e0F0B091Z090B0F4_2^4p0A5a4U5N024e5R0s0v2e5W5$570(4W025e5F5M0t5I025l2Q5b0(5!5/5w5'4=4A0c4C5m5 0t4p055Y3k5{5}3'6a4p0b5K5G3k5y0l3m623d526s3k0u0x525E2'6n4#0-0i1Z4j6e3K4+6I3Y5{3$5~5%6b0-5#5f6a4v026A3}6j4|5q2O5s5u5L6V5O5Q5S5U5.696Q616U6Q6W5)0B5+5-5X6?5:0t5=5@6B5_6K5r6(6(5_0G4$5(5P6L4{4q7e587c6,6{0Q6/6P6 6=5^6*7j5R5T0G5V6}7o636R020L6T6%775u794w4y66687z5Z0-6d6:6 6W7y6i6;0-6l6~7A5=0w6v3R6+7u6.7U6Z7W027E2'6'786!7C6m5_5y5A5C6Y4S797b4e7h600-4,7N3k6^5P5*5,7m7+2j746S7%4u7(6-7w7n7V7p4|3r0C3 0c2k2L8t3*1k3,2n2q2l0s1B8w0C3+0/8G0T0V0X02.

Indice 1

On peut envisager de savoir combien la girafe a pu manger au maximum en arrivant à un arbre i :

sans avoir mangé sur le précédent, auquel cas elle pourra manger ici, en i
en ayant mangé au précédent, auquel cas elle ne pourra manger ici, en i

Indice 2

On utilisera deux variables :

maxi_sans_i : la quantité maximale que la girafe peut manger sans pouvoir manger à la position i,
maxi_avec_i : la quantité maximale que la girafe peut manger avec la position i dévorée.

Indice 3

On gèrera les cas avec peu d'arbres. Aucun arbre ; aucune feuille.
On initialisera correctement les variables.
On mettra en place avec prudence la boucle qui permet de progresser jusqu'au bout de la file d'arbres.