Jakie jest prawidłowe podejście do rozwiązania SPOJ DIEHARD?

Question

Próbowałem rozwiązać pytanie dotyczące praktyki w sprawie SPOJ https://www.spoj.pl/problems/DIEHARD/. Jednak oba moje chciwe podejście spowodowało Wrong Answer i rekurencja była zbyt wolna dla najgorszego przypadku.Czy ktoś może powiedzieć, jak podejść do tego problemu? Szukam kogoś, kto wskaże mi właściwy kierunek.

Gra jest prosta. Początkowo masz "H" ilość zdrowia i "A" ilość zbroi. W każdej chwili możesz żyć w dowolnym z trzech miejsc - ognia, wody i powietrza. Po każdej jednostce czasu musisz zmienić miejsce zamieszkania. Na przykład, jeśli obecnie żyjesz w ogniu, możesz wejść do wody lub powietrza.

• Jeśli krok w powietrzu, swojego zdrowia wzrasta o 3 i pancerz zwiększa się o 2
• Jeśli wejdziesz do wody, twoje spadki zdrowia o 5 i wasze spadki pancerz o 10
  Jeśli krok w ogniu Twoje zdrowie zmniejsza się o 20 i pancerz zwiększa się o 5

Jeśli twoje zdrowie lub pancerz staje < = 0, umrzesz natychmiast

Znajdź maksymalny czas można przetrwać.

Wejście:

Pierwsza linia składa się z liczb całkowitych t, ​​liczba testowych. Dla każdego przypadku testowego będą dwie dodatnie liczby całkowite reprezentujące początkowe zdrowia H i początkowy pancerza A.

wyjściowa:

Dla każdego przypadku testowego znaleźć maksymalny czas można przetrwać.

Answer 1

Czy próbowałeś DFS? Państwo jest krotką (powietrze | ogień | woda, H, A). To ma:

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

Zrób DFS na nim i znajdź najwyższe ruchy. (Tzn ustawić wszystko na -1 i stanów początkowych 0, następnie DFS od 0 do stanów wszystkich pozycjach osiągalnych)

Answer 2

Oto kolejny sposób na to analitycznie:

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 

Maksymalizacja M. Można zrobić to przez binarne wyszukiwanie M lub możesz użyć programowania liniowego.

Binary wyszukiwania pętla:

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; 

W każdym przypadku korzystania z podstawowych algebry gimnazjum uprościć nierównościami/równanie.

Answer 3

Zrobiłem przy użyciu dynamicznego progamowania. Dp [zdrowie] [zbroja] [powietrze/ogień/woda] - to maksymalny czas, jaki możesz przeżyć, jeśli zaczynasz od tego warunku , a następnie warunki powtarzające się stają po prostu Dp [zdrowie] [zbroja] [powietrze/ogień/woda ] = 1 + maks. Następnych stanów, które możesz przejść do Oczywiście podstawowym przypadkiem jest to, że może dojść donikąd, więc odpowiedź na to staje się równa zero.

Answer 4

Dobra, po pierwsze spróbuj to rozwiązać chciwym podejściem. Oczywistym jest, że powietrze jest najlepszym wyborem, ponieważ zwiększa zarówno pancerz, jak i zdrowie, ale można jechać naprzemiennie tylko na przemian. Tak więc każdy nieparzysty (tj. 1,3,5 ...) ruch będzie w powietrzu. Teraz musimy zdecydować, co zrobić z równomiernymi ruchami?

Mamy dwie możliwości Ogień lub woda? Musimy być rozsądni i wybrać taki ruch, który utrzymuje zarówno H, jak i A powyżej 0. Teraz skoki w ogniu kosztują zdrowie -20, mimo że zwiększają zbroję o 5, ale hej czekaj, jaki jest pożytek ze zwiększonego pancerza, jeśli nie t zdobądź zdrowie> 0. Więc jeśli H> 5 i A> 10 wybierz wodę.

Co teraz, jeśli brakuje nam zbroi, ale mamy wystarczająco dużo zdrowia? W takim przypadku nie mamy innego wyboru, jak przejść do ognia.

Więc teraz mamy chciwy podejście:

Tak więc, jeśli mamy wystarczającą hi, pójdziemy do wody. W przeciwnym razie, jeśli H jest wystarczające, a A nie wystarcza, idź do ognia. Innym, to koniec!

Oto link ideone realizacji: 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; 
}