A ve B olmak üzere iki tür gücünüzün olduğu ve 3 tür X, Y ve Z Alanının olduğu bir oyun düşünün. Her saniye bu alanlar arasında geçiş yapmanız gerekir ve her alanın, A ve B gücünüzün artmasına veya azalmasına neden olan belirli özellikleri vardır. Hayatta kalma süremizi maksimuma çıkaracak şekilde alanları seçmeye devam etmeliyiz. Hayatta kalma süresi, A veya B güçlerinden herhangi biri 0'ın altına düştüğünde sona erer.
Örnekler:
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
Bu sorun, herhangi bir bölgeye gidebileceğimiz her zaman biriminden sonra özyineleme kullanılarak çözülebilir, ancak sonuçta maksimum hayatta kalma süresine yol açan alanı seçeceğiz. Özyineleme aynı alt problemin birçok kez çözülmesine yol açabileceğinden, sonucu A ve B gücüne göre not edeceğiz, eğer aynı A ve B gücü çiftine ulaşırsak, onu tekrar çözmeyeceğiz, bunun yerine önceden hesaplanan sonucu alacağız.
Aşağıda verilen, yukarıdaki yaklaşımın basit bir uygulamasıdır.
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>
Çıkış
5