Predstavte si hru, v ktorej máte dva typy schopností A a B a existujú 3 typy oblastí X Y a Z. Každú sekundu musíte medzi týmito oblasťami prepínať a každá oblasť má špecifické vlastnosti, o ktoré sa vaša sila A a sila B zvyšuje alebo znižuje. Musíme si naďalej vyberať oblasti takým spôsobom, aby sme maximalizovali čas prežitia. Čas prežitia končí, keď ktorákoľvek z mocnín A alebo B dosiahne menej ako 0.
Príklady:
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
Tento problém sa dá vyriešiť pomocou rekurzie po každej časovej jednotke, po ktorej môžeme ísť do ktorejkoľvek oblasti, ale vyberieme si tú oblasť, ktorá v konečnom dôsledku vedie k maximálnemu času prežitia. Keďže rekurzia môže viesť k riešeniu rovnakého podproblému mnohokrát, zapamätáme si výsledok na základe mocniny A a B, ak sa dostaneme k rovnakému páru mocniny A a B, nebudeme to riešiť znova, namiesto toho vezmeme predtým vypočítaný výsledok.
Nižšie je uvedená jednoduchá implementácia vyššie uvedeného prístupu.
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>
Výstup
5