두 가지 유형의 파워 A와 B가 있고 3가지 유형의 X, Y 및 Z 영역이 있는 게임을 생각해 보세요. 매초마다 이 영역 사이를 전환해야 하며 각 영역에는 파워 A와 파워 B가 증가하거나 감소하는 특정 속성이 있습니다. 우리는 생존 시간을 최대화하는 방식으로 계속해서 지역을 선택해야 합니다. 생존 시간은 A 또는 B 전력 중 하나가 0 미만에 도달하면 종료됩니다.
mysql이 같지 않음
예:
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
이 문제는 각 시간 단위 후에 재귀를 사용하여 해결될 수 있습니다. 우리는 어떤 영역으로든 갈 수 있지만 궁극적으로 최대 생존 시간으로 이어지는 영역을 선택합니다. 재귀는 동일한 하위 문제를 여러 번 해결하게 할 수 있으므로 동일한 A와 B 쌍에 도달하면 A와 B의 거듭제곱을 기준으로 결과를 기억합니다. 대신 이전에 계산된 결과를 사용하여 다시 해결하지 않습니다.
아래에는 위 접근 방식의 간단한 구현이 나와 있습니다.
Java의 arraylist 정렬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>
산출
5