Cách tiếp cận chính xác để giải quyết SPOJ DIEHARD là gì?

Question

Tôi đã cố gắng giải quyết một câu hỏi thực hành trên SPOJ https://www.spoj.pl/problems/DIEHARD/. Tuy nhiên cả hai cách tiếp cận tham lam của tôi dẫn đến câu trả lời sai và đệ quy quá chậm đối với trường hợp xấu nhất. Có ai biết cách tiếp cận vấn đề này không? Tôi đang tìm ai đó để chỉ cho tôi đi đúng hướng.

Trò chơi rất đơn giản. Ban đầu, bạn có số lượng sức khỏe 'H' và lượng áo giáp 'A'. Bất cứ lúc nào bạn có thể sống ở bất kỳ nơi nào trong ba nơi - lửa, nước và không khí. Sau mỗi lần đơn vị, bạn phải thay đổi nơi ở của mình. Ví dụ nếu bạn hiện đang sống trong lửa, bạn có thể bước vào nước hoặc không khí.

• Nếu bạn bước vào không khí, bạn tăng sức khỏe của 3 và áo giáp của bạn tăng 2
• Nếu bạn bước vào nước, giảm sức khỏe của bạn bằng 5 và áo giáp của bạn giảm 10
  Nếu bạn bước vào lửa , giảm sức khỏe của bạn bằng 20 và áo giáp của bạn tăng 5

Nếu sức khỏe hoặc áo giáp của bạn trở nên < = 0, bạn sẽ chết ngay lập tức

Tìm thời gian tối đa mà bạn có thể sống sót.

Nhập:

Dòng đầu tiên bao gồm số nguyên t, số lượng trường hợp thử nghiệm. Đối với mỗi trường hợp thử nghiệm sẽ có hai số nguyên dương đại diện cho H sức khỏe ban đầu và ban đầu giáp A.

Output:

Đối với mỗi trường hợp thử nghiệm tìm ra thời gian tối đa mà bạn có thể sống sót.

Answer 1

Bạn đã thử DFS chưa? Trạng thái là một tuple (air | fire | water, H, A). Điều này có:

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

Thực hiện DFS trên đó và tìm di chuyển cao nhất. (Tức là thiết lập tất cả mọi thứ để các quốc gia -1 và ban đầu là 0, sau đó DFS từ 0 bang cho tất cả các vị trí có thể truy cập)

Answer 2

Đây là một cách khác để làm điều đó phân tích:

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 

Tối đa hóa M. Bạn có thể làm điều này bằng cách tìm kiếm nhị phân M, hoặc bạn có thể sử dụng lập trình tuyến tính.

Binary tìm kiếm vòng lặp:

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; 

Trong cả hai trường hợp sử dụng đại số học cơ bản để đơn giản hóa việc bất bình đẳng/phương trình.

Answer 3

Tôi đã thực hiện bằng cách sử dụng tính năng tích hợp động. Dp [y tế] [giáp] [không khí/lửa/nước] - là thời gian tối đa bạn có thể sống nếu bạn bắt đầu từ điều kiện này thì điều kiện tái phát chỉ đơn giản là trở thành Dp [health] [armor] [air/fire/water ] = 1 + tối đa các trạng thái tiếp theo bạn có thể truy cập Rõ ràng trường hợp cơ sở là khi anh ta không thể đi đến đâu nên câu trả lời cho điều đó trở thành 0.

Answer 4

Được rồi, Trước hết hãy thử giải quyết bằng cách tiếp cận tham lam. Rõ ràng là không khí là lựa chọn tốt nhất có thể vì nó làm tăng cả áo giáp và sức khỏe nhưng bạn chỉ có thể lên không trung luân phiên. Vì vậy, mọi động tác kỳ quặc (tức là 1,3,5 ...) sẽ được phát sóng. Bây giờ chúng ta phải quyết định phải làm gì với những động tác thậm chí?

Vì vậy, chúng tôi có hai lựa chọn Lửa hoặc nước? Chúng ta phải hợp lý và chọn một động thái giữ cả H và A trên 0. Bây giờ nhảy vào lửa tốn sức khỏe -20 mặc dù nó tăng giáp lên 5, nhưng chờ đã, việc sử dụng giáp tăng nếu bạn không ' t nhận được sức khỏe của bạn> 0. Vì vậy, nếu H> 5 và A> 10 chọn nước.

Bây giờ điều gì xảy ra nếu chúng ta thiếu giáp nhưng có đủ sức khỏe? Trong trường hợp đó, chúng tôi không có lựa chọn nào khác ngoài việc nhảy lên lửa.

Vì vậy, bây giờ chúng tôi có một cách tiếp cận tham lam:

Vì vậy, nếu chúng tôi có đủ H và A, chúng tôi sẽ đi đến nước. Khác, nếu H là đủ và A là không đủ, hãy đi lửa. Khác, kết thúc!

Dưới đây là liên kết ideone thực hiện: 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; 
}