Considera un gioco in cui hai due tipi di poteri A e B e ci sono 3 tipi di aree X Y e Z. Ogni secondo devi passare da un'area all'altra e ciascuna area ha proprietà specifiche in base alle quali il tuo potere A e il potere B aumentano o diminuiscono. Dobbiamo continuare a scegliere le aree in modo tale da massimizzare il nostro tempo di sopravvivenza. Il tempo di sopravvivenza termina quando uno qualsiasi dei poteri A o B raggiunge meno di 0.
Esempi:
Initial value of Power A = 20 Initial value of Power B = 8 Area X (3 2) : If you step into Area X A increases by 3 B increases by 2 Area Y (-5 -10) : If you step into Area Y A decreases by 5 B decreases by 10 Area Z (-20 5) : If you step into Area Z A decreases by 20 B increases by 5 It is possible to choose any area in our first step. We can survive at max 5 unit of time by following these choice of areas : X -> Z -> X -> Y -> X
Questo problema può essere risolto utilizzando la ricorsione dopo ogni unità di tempo in cui possiamo andare in una qualsiasi delle aree, ma sceglieremo quell'area che alla fine porta al massimo tempo di sopravvivenza. Poiché la ricorsione può portare a risolvere lo stesso sottoproblema più volte, memorizzeremo il risultato sulla base delle potenze A e B, se raggiungiamo la stessa coppia di potenze A e B non lo risolveremo di nuovo, prenderemo invece il risultato calcolato in precedenza.
Di seguito è riportata la semplice implementazione dell'approccio di cui sopra.
CPP// C++ code to get maximum survival time #include
/*package whatever //do not write package name here */ import java.util.*; import java.io.*; class GFG { // Java code to get maximum survival time // class to represent an area static class area { // increment or decrement in A and B public int a b; public area(int a int b){ this.a = a; this.b = b; } }; // class to represent pair static class Pair{ public int firstsecond; public Pair(int firstint second){ this.first = first; this.second = second; } } // Utility method to get maximum of 3 integers static int max(int a int b int c) { return Math.max(a Math.max(b c)); } // Utility method to get maximum survival time static int maxSurvival(int A int B area X area Y area Z int last HashMap<Pair Integer> memo) { // if any of A or B is less than 0 return 0 if (A <= 0 || B <= 0) return 0; Pair cur = new Pair(A B); // if already calculated return calculated value if (memo.containsKey(cur)) return memo.get(cur); int temp = 0; // step to areas on basis of last choose area switch(last) { case 1: temp = 1 + Math.max(maxSurvival(A + Y.a B + Y.b X Y Z 2 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)); break; case 2: temp = 1 + Math.max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)); break; case 3: temp = 1 + Math.max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Y.a B + Y.b X Y Z 2 memo)); break; } // store the result into map memo.put(curtemp); return temp; } // method returns maximum survival time static int getMaxSurvivalTime(int A int B area X area Y area Z) { if (A <= 0 || B <= 0) return 0; HashMap<PairInteger> memo = new HashMap<>(); // At first we can step into any of the area return max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Y.a B + Y.b X Y Z 2 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)); } // Driver Code public static void main(String args[]) { area X = new area(3 2); area Y = new area(-5 -10); area Z = new area(-20 5); int A = 20; int B = 8; System.out.println(getMaxSurvivalTime(A B X Y Z)); } } // This code is contributed by shinjanpatra
# Python code to get maximum survival time # Class to represent an area class area: def __init__(self a b): self.a = a self.b = b # Utility method to get maximum survival time def maxSurvival(A B X Y Z last memo): # if any of A or B is less than 0 return 0 if (A <= 0 or B <= 0): return 0 cur = area(A B) # if already calculated return calculated value for ele in memo.keys(): if (cur.a == ele.a and cur.b == ele.b): return memo[ele] # step to areas on basis of last chosen area if (last == 1): temp = 1 + max(maxSurvival(A + Y.a B + Y.b X Y Z 2 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)) elif (last == 2): temp = 1 + max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)) elif (last == 3): temp = 1 + max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Y.a B + Y.b X Y Z 2 memo)) # store the result into map memo[cur] = temp return temp # method returns maximum survival time def getMaxSurvivalTime(A B X Y Z): if (A <= 0 or B <= 0): return 0 memo = dict() # At first we can step into any of the area return max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Y.a B + Y.b X Y Z 2 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)) # Driver code to test above method X = area(3 2) Y = area(-5 -10) Z = area(-20 5) A = 20 B = 8 print(getMaxSurvivalTime(A B X Y Z)) # This code is contributed by Soumen Ghosh.
// C# code to get maximum survival time using System; using System.Collections.Generic; class GFG { // class to represent an area class area { // increment or decrement in A and B public int a b; public area(int a int b) { this.a = a; this.b = b; } }; // class to represent pair class Pair { public int first second; public Pair(int first int second) { this.first = first; this.second = second; } } // Utility method to get maximum of 3 integers static int max(int a int b int c) { return Math.Max(a Math.Max(b c)); } // Utility method to get maximum survival time static int maxSurvival(int A int B area X area Y area Z int last Dictionary<Pair int> memo) { // if any of A or B is less than 0 return 0 if (A <= 0 || B <= 0) return 0; Pair cur = new Pair(A B); // if already calculated return calculated value if (memo.ContainsKey(cur)) return memo[cur]; int temp = 0; // step to areas on basis of last choose area switch (last) { case 1: temp = 1 + Math.Max(maxSurvival(A + Y.a B + Y.b X Y Z 2 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)); break; case 2: temp = 1 + Math.Max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)); break; case 3: temp = 1 + Math.Max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Y.a B + Y.b X Y Z 2 memo)); break; } // store the result into map memo[cur] = temp; return temp; } // method returns maximum survival time static int getMaxSurvivalTime(int A int B area X area Y area Z) { if (A <= 0 || B <= 0) return 0; Dictionary<Pair int> memo = new Dictionary<Pair int>(); // At first we can step into any of the area return max( maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Y.a B + Y.b X Y Z 2 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)); } // Driver Code public static void Main(String[] args) { area X = new area(3 2); area Y = new area(-5 -10); area Z = new area(-20 5); int A = 20; int B = 8; Console.WriteLine( getMaxSurvivalTime(A B X Y Z)); } } // This code is contributed by lokeshpotta20.
<script> // JavaScript code to get maximum survival time // Class to represent an area class area{ constructor(a b){ this.a = a this.b = b } } // Utility method to get maximum survival time function maxSurvival(A B X Y Z last memo){ // if any of A or B is less than 0 return 0 if (A <= 0 || B <= 0) return 0 let cur = new area(A B) // if already calculated return calculated value for(let [keyvalue] of memo){ if (cur.a == key.a && cur.b == key.b) return memo.get(key) } let temp; // step to areas on basis of last chosen area if (last == 1){ temp = 1 + Math.max(maxSurvival(A + Y.a B + Y.b X Y Z 2 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)) } else if (last == 2){ temp = 1 + Math.max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)) } else if (last == 3){ temp = 1 + Math.max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Y.a B + Y.b X Y Z 2 memo)) } // store the result into map memo.set(cur temp) return temp } // method returns maximum survival time function getMaxSurvivalTime(A B X Y Z){ if (A <= 0 || B <= 0) return 0 let memo = new Map() // At first we can step into any of the area return Math.max(maxSurvival(A + X.a B + X.b X Y Z 1 memo) maxSurvival(A + Y.a B + Y.b X Y Z 2 memo) maxSurvival(A + Z.a B + Z.b X Y Z 3 memo)) } // Driver code to test above method let X = new area(3 2) let Y = new area(-5 -10) let Z = new area(-20 5) let A = 20 let B = 8 document.write(getMaxSurvivalTime(A B X Y Z)'') // This code is contributed by shinjanpatra </script>
Produzione
5