Elección de área

Considere un juego, en el que tiene dos tipos de poderes, A y B y hay 3 tipos de Áreas X, Y y Z. Cada segundo tiene que cambiar entre estas áreas, cada área tiene propiedades específicas por las cuales su poder A y aumentar o disminuir la potencia B. Necesitamos seguir eligiendo áreas de tal manera que se maximice nuestro tiempo de supervivencia. El tiempo de supervivencia termina cuando cualquiera de las potencias, A o B, llega a menos de 0. 
Ejemplos: 
 

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

Este problema se puede resolver usando la recursividad, después de cada unidad de tiempo podemos ir a cualquier área, pero elegiremos esa área que finalmente nos lleva al máximo tiempo de supervivencia. Como la recursividad puede llevar a resolver el mismo subproblema muchas veces, memorizaremos el resultado en base a las potencias A y B, si llegamos al mismo par de potencias A y B, no lo resolveremos de nuevo sino que tomaremos el calculado previamente. resultado. 
A continuación se muestra la implementación simple del enfoque anterior. 
 

//  C++ code to get maximum survival time
#include <bits/stdc++.h>
using namespace std;
 
//  structure to represent an area
struct area
{
    //  increment or decrement in A and B
    int a, b;
    area(int a, int b) : a(a), b(b)
    {}
};
 
//  Utility method to get maximum of 3 integers
int max(int a, int b, int c)
{
    return max(a, max(b, c));
}
 
//  Utility method to get maximum survival time
int maxSurvival(int A, int B, area X, area Y, area Z,
                int last, map<pair<int, int>, int>& memo)
{
    //  if any of A or B is less than 0, return 0
    if (A <= 0 || B <= 0)
        return 0;
    pair<int, int> cur = make_pair(A, B);
 
    //  if already calculated, return calculated value
    if (memo.find(cur) != memo.end())
        return memo[cur];
 
    int temp;
 
    //  step to areas on basis of last choose area
    switch(last)
    {
    case 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));
        break;
    case 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));
        break;
    case 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));
        break;
    }
 
    //  store the result into map
    memo[cur] = temp;
 
    return temp;
}
 
//  method returns maximum survival time
int getMaxSurvivalTime(int A, int B, area X, area Y, area Z)
{
    if (A <= 0 || B <= 0)
        return 0;
    map< pair<int, int>, int > memo;
 
    //  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
int main()
{
    area X(3, 2);
    area Y(-5, -10);
    area Z(-20, 5);
 
    int A = 20;
    int B = 8;
    cout << getMaxSurvivalTime(A, B, X, Y, Z);
 
    return 0;
}

/*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 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, 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(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;
    HashMap<Pair,Integer> 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))
    else if (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))
    else if (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.

<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 [key,value] 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),"</br>")
 
   
// This code is contributed by shinjanpatra
 
</script>

Producción: 
 

5

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.