区域选择-yiteyi-C++库

考虑一个游戏，你有两种类型的功率A和B，有3种类型的区域X，Y和Z。每秒钟你必须在这些区域之间切换，每个区域都有特定的属性，通过这些属性，你的功率A和功率B增加或减少。我们需要不断地选择区域，以使我们的生存时间最大化。当A或B的任一次幂小于0时，生存时间结束。例如：

null

Initial value of Power A = 20        Initial value of Power B = 8Area X (3, 2) : If you step into Area X,                 A increases by 3,                 B increases by 2Area Y (-5, -10) : If you step into Area Y,                    A decreases by 5,                    B decreases by 10Area Z (-20, 5) : If you step into Area Z,                   A decreases by 20,                   B increases by 5It 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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个问题可以通过递归来解决，在每个时间单位后，我们可以去任何一个区域，但我们会选择最终导致最大生存时间的区域。由于递归可能导致多次求解同一个子问题，我们将根据幂A和幂B来记忆结果，如果我们达到相同的幂A和幂B对，我们将不再求解它，而是取之前计算的结果。下面给出了上述方法的简单实现。

CPP

                         //  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 chose 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;                       
                         }                       

Python3

                         # 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.                       

输出：

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章