7

SPOJ https://www.spoj.pl/problems/DIEHARD/の練習問題を解こうとしていました。しかし、私の貪欲なアプローチは間違った答えをもたらし、再帰は最悪の場合には遅すぎました.誰かがこの問題にアプローチする方法を教えてもらえますか? 私を正しい方向に向けてくれる人を探しています。

ゲームはシンプルです。最初は「H」のヘルスと「A」のアーマーがあります。いつでも、火、水、空気の 3 つの場所のどこにでも住むことができます。単位時間ごとに、住む場所を変えなければなりません。たとえば、現在火の中で生活している場合、水または空気に足を踏み入れることができます。

  • 空中に足を踏み入れると、ヘルスが 3 増加し、アーマーが 2 増加します。
  • 水に足を踏み入れると、ヘルスが 5 減少し、アーマーが 10 減少し
    ます 火に足を踏み入れると、ヘルスが 20 減少し、アーマーが 5 増加します

ヘルスまたはアーマーが 0 以下になると、即死します。

あなたが生き残ることができる最大の時間を見つけてください。

入力：

最初の行は、テスト ケースの数である整数 t で構成されます。各テスト ケースには、初期ヘルス H と初期アーマー A を表す 2 つの正の整数があります。

出力：

テストケースごとに、生き残ることができる最大時間を見つけてください。

4

4 に答える 4

5

よし、まずは貪欲なアプローチで解いてみる。空気は鎧と健康の両方を増加させるため、可能な限り最良の選択であることは明らかですが、交互にしか空気に行くことができません. したがって、すべての奇数 (つまり、1、3、5...) の移動は空中になります。次に、偶数の移動をどうするかを決定する必要がありますか?

火か水か？合理的に考えて、H と A の両方を 0 より大きく保つような動きを選択する必要があります。現在、火の中をジャンプすると、アーマーが 5 増加しますが、ヘルスが -20 かかりますが、ちょっと待ってください。 t get your health >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 になります。 +あなたが行くことができる次の状態の最大数 明らかに基本的なケースは、彼がどこにも行けないときであり、そのための答えはゼロになります。

于 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を試しましたか？状態は (air|fire|water, H, A) のタプルです。これは持っています：

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

その上で DFS を実行し、最高の動きを見つけます。(つまり、すべてを -1 に設定し、初期状態を 0 に設定してから、0 状態からすべての到達可能な位置に DFS を設定します)

于 2012-10-19T14:41:29.967 に答える