7

我试图解决关于 SPOJ https://www.spoj.pl/problems/DIEHARD/的练习题。然而，我的贪婪方法都导致了错误的答案，并且递归对于最坏的情况来说太慢了。谁能告诉如何解决这个问题？我正在寻找可以为我指明正确方向的人。

游戏很简单。你最初有“H”的生命值和“A”的护甲。在任何时候，你都可以生活在三个地方——火、水和空气中的任何一个。在每单位时间之后，你必须改变你的居住地。例如，如果您目前生活在火灾中，您可以踏入水中或空气中。

  • 如果你踏入空中，你的健康增加 3 点，你的护甲增加 2 点
  • 如果你踏入水中，你的生命值减少 5，你的护甲减少 10
    如果你踏入火中，你的生命值减少 20，你的护甲增加 5

如果您的生命值或护甲变为 <=0，您将立即死亡

找到你可以生存的最长时间。

输入：

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

输出：

对于每个测试用例，找到您可以生存的最长时间。

4

4 回答 4

5

好的，首先尝试通过贪婪的方法解决它。很明显，空气是最好的选择，因为它可以增加护甲和生命值，但你只能交替使用空气。所以每一个奇数（即 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;
}
于 2015-05-01T06:40:33.663 回答
1

我通过使用动态编程做到了。Dp[health][armour][air/fire/water]- 是你可以活的最长时间，如果你从这个条件开始，那么反复出现的条件就变成 Dp[health][armour][air/fire/water]=1 +max of next states you can go to Obviousy 基本情况是他无处可去，因此答案为零。

于 2012-11-10T10:12:39.967 回答
1

这是另一种分析方法：

a = number of times visiting air state
F = number of times visiting fire state
W = number of times visiting water state

M = a + F + W  // total moves

// positive
a >= 0
F >= 0
W >= 0

// because of the restriction of moving between states...
a <= F + W + 1
F <= W + a + 1
W <= a + F + 1

// the effect of armor and health...
H < -3a + 5H + 20F
A < -2a + 10W - 5F

最大化 M。您可以通过对 M 进行二进制搜索来做到这一点，也可以使用线性规划。

二分查找循环：

int ok = 0;
int impossible = 1000000000;
while (impossible - ok > 1)
{
    int candidate = ok + (impossible-ok) / 2;

    if (check(candidate))
        ok = candidate;
    else
        impossible = candidate;
}
return ok;

在任何一种情况下，都使用基本的高中代数来简化不等式/方程。

于 2012-10-19T15:26:24.003 回答
0

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

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

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

于 2012-10-19T14:41:29.967 回答