解决SPOJ DIEHARD的正确方法是什么？

Question

我试图在SPOJ https://www.spoj.pl/problems/DIEHARD/上解决练习题.然而,我的贪婪方法导致错误的答案和递归对于最坏的情况来说太慢.任何人都可以告诉如何解决这个问题？我正在寻找有人指出我正确的方向.

游戏很简单.你最初有'H'的健康和'A'量的护甲.在任何时刻,您都可以居住在三个地方中的任何一个地方 - 火,水和空气.每个单位时间之后,你必须改变你的生活地点.例如,如果您目前生活在火中,您可以步入水中或空气中.

• 如果你进入空中,你的生命值会增加3点,你的护甲会增加2点
• 如果你进入水中,你的生命值会降低5点,你的护甲会降低10点.
  如果你步入火中,你的生命值会降低20点而你的护甲会增加5点

如果你的健康或护甲<= 0,你会立即死亡

找到你能活下来的最长时间.

输入:

第一行包含整数t,即测试用例的数量.对于每个测试用例,将有两个正整数代表初始健康H和初始护甲A.

输出:

对于每个测试用例,找到您可以存活的最长时间.

Answer 1

好的，首先尝试用贪心法解决它。显然，空气是最好的选择，因为它可以增加护甲和生命值，但你只能交替进入空气。因此，每一个奇数（即 1、3、5...）的举动都会播出。现在我们必须决定如何处理偶数移动？

那么我们有两个选择 火还是水？我们必须保持理性，选择这样的动作，使 H 和 A 都保持在 0 以上。现在在火中跳跃会消耗生命值 -20，尽管它会增加 5 的护甲值，但是嘿等等，如果你不这样做，增加的护甲值有什么用呢？ t 让你的健康 >0 。因此，如果 H>5 且 A>10，则选择水。

现在，如果我们缺少护甲但有足够的生命值怎么办？在这种情况下，我们别无选择，只能跳下去开火。

所以现在我们有一个贪心的方法：

所以，如果我们有足够的 H 和 A，我们就会去喝水。否则，如果H足够而A不够，就开火。不然就完了！

这是ideone的实现链接： http://ideone.com/rkobNK

#include<stdio.h>
int main(){
    long long int x,i,a,b,t,h,arm;
    scanf("%lld",&x);
    for(i=0;i<x;i++){
        scanf("%lld %lld",&a,&b);
        if(a==0||b==0)
         printf("0\n");
        else{
            t=1;
            h=a+3;
            arm=b+2;
            while(1){
                if(h>5&&arm>10){
                    h=h-2;
                    arm=arm-8;
                    t=t+2;
                }else if(h>20&&arm<=10){
                    h=h-17;
                    arm=arm+7;
                    t=t+2;
                }else {
                    printf("%lld\n",t);
                    break;
                }
            }
     }
    }
    return 0;
} 

Answer 2

你试过DFS吗？状态是（空气|水，H，A）的元组。这有：

3 * 1000 * 1000 = 3,000,000 game states

对它进行 DFS 并找到最高的移动。（即将所有内容设置为-1，初始状态设置为0，然后从0状态到所有可到达位置的DFS）