Cần giúp đỡ thuật toán đơn giản hoá con đường trên hệ toạ độ

Binh_Pham_Van · August 28, 2019, 1:55pm

Mình muốn hỏi ý tưởng và thuật toán của bài này:

(Croatia HSIN 2005 - THCS - ngày 1, bài 3) Tưởng tượng một con đường đơn giản trong hệ toạ độ. Đường đi từ trái sang phải theo hình dạng của mặt đất và trong một ô có thể: giữ nguyên độ cao, đi lên hoặc đi xuống 1 ô.
Ô tô đi trên con đường theo hướng từ trái sang phải. Thời gian cần thiết để đi thẳng qua 1 ô là A giây, và lên hoặc xuống I ô là B giây.

Tuy vậy, chúng ta có thể xây dựng một đường hầm dưới những ngọn núi hay một chiếc cầu qua những thung lũng. Những đường hầm hay cầu được xây dựng phải được nằm ngang, chỉ giao cắt với con đường tại 2 điểm đầu cuối, và thời gian cần để ô tô di chuyển qua một ô bằng đường hầm hoặc qua cầu là C giây.

Viết chương trình tính toán thời gian ngắn nhất để ô tô đi hết cả quãng đường qua những đường hầm và cầu tốt nhất, với hình dạng mặt đất cho trước. Tổng số đường hầm hoặc câu xây dựng không lớn hơn số K cho trước.

Dữ liệu: vào từ file inp.txt

Dòng đầu tiên chứa 3 số nguyên A, B, và C, 1 <= A, B, C <= 100.
Dòng thứ 2 chứa 2 số nguyên N và K, 1 <= N <= 30000, 1 <= K <= 1000.
Dòng thứ 3 chứa dãy kí hiệu mô tả mặt đất từ trái sang phải, trong đó:

‘D’ nếu ô tiếp theo trên mặt đất có hướng đi xuống.
‘R’ nếu ô tiếp theo trên mặt đất giữ nguyên độ cao.
‘G’ nếu ô tiếp theo trên mặt đất có hướng đi lên.

Kết quả: Ghi ra file out.txt thời gian ngắn nhất kết quả của đề bài đã cho.

INP.TXT:

10 20 15

16 2

RGRDGGDDRRDDRDGG

OUT.TXT:
235

Hình minh hoạ cho ví dụ:
Capture

Cảm ơn các bạn.

kisuluoibieng · August 27, 2019, 9:39am

vậy rốt cuộc D là lên hay xuống?

Binh_Pham_Van · August 27, 2019, 9:41am

Sorry, mình nhầm, là G đi xuống chứ không phải D.

Phong_Ky_Vo · August 28, 2019, 9:15am

Hi Phạm Văn Bình.
Bạn thử thuật toán tìm đường đi ngắn nhất trên đồ thì xem.

tntxtnt · August 28, 2019, 4:06pm

Dijkstra thôi mà :V

Mà đề THCS gì khó vậy :V

tntxtnt · August 28, 2019, 7:31pm

đáp án: :V http://www.hsin.hr/2005/ (National Competition #1 10th May 2005 Juniors )

Consider the function f(k, x), the smallest possible amount of time in which we can reach position x, having till now built exactly k tunnels or viaducts.
Let right(x) correspond to the first position to the right of x where the height is the same as the height of position x.
We can now use f(k, x) to calculate the following values:
f(k, x+1) - if we proceed to position x+1 without building a tunnel or viaduct
f(k+1, right(x)) - if we build a tunnel or viaduct starting at position x and ending at position right(x)
We can use dynamic programming to calculate f(k, x) for all values of k and x. Note that we don’t have enough memory available to hold the entire table, but we can get away with storing only two rows (for k and k+1) at all times.

code của nó 2 vòng for vậy là O(k*n) rồi :V

spoiler

   scanf( "%d%d%d%d%d ", &A, &B, &C, &N, &M );
   ...
   int rjesenje = inf;
   for( int K = 0; K <= M; ++K ) {
      int k = K%2;
      int kplus1 = (K+1)%2;

      for( int x = 0; x <= N; ++x ) a[kplus1][x] = inf;
      for( int x = 0; x < N; ++x ) {
         if( visina[x+1] == visina[x]+1 ) a[k][x+1] <?= a[k][x] + B;
         if( visina[x+1] == visina[x]   ) a[k][x+1] <?= a[k][x] + A;
         if( visina[x+1] == visina[x]-1 ) a[k][x+1] <?= a[k][x] + B;
         if( desno[x] != -1 ) a[kplus1][desno[x]] <?= a[k][x] + C*(desno[x]-x);
      }
      rjesenje <?= a[k][N];
   }

rogp10 · July 15, 2020, 5:59am

Cái này là GCC extension! (giờ bỏ rồi nên bỏ vào máy chạy ko đc!)

      minh <?= visina[i];
      maxh >?= visina[i];

dịch ra là

   minh = std::min(minh, visina[i]);
   maxh = std::max(maxh, visina[i]);

tntxtnt · August 28, 2019, 5:34pm

ai biết đâu giải nén ra thấy nó ghi vậy =]]

đừng đòi hỏi đáp án của mấy kì thi thuật toán này tuân theo standard =]]

rogp10 · September 1, 2019, 10:09am

Tới đoạn này mới là hại não khúc tìm đoạn thì trải slot thay vì dùng hash.

Input/Output mẫu

height = [0 0 1 1 0 1 2 1 0 0 0 -1 -2 -2 -3 -2 -1]
ranges = [1…4, 3…5, 5…7, 4…8, 11…16]
value = [5, 10, 10, 20, 15]
saved = 20+15 = 35
original_cost = 270

Vậy là vô tình mình giải đúng mỗi case này thôi mỗi bước lặp ta chỉ sử dụng một đường hầm duy nhất, mảng 1 dùng đường hầm tính cho mảng 2.

rogp10 · September 1, 2019, 11:54am

Sửa lại giảm hẳn số lần copy

spoiler

--- autoput.cpp
+++ autoput.cpp
@@ -52,2 +52,2 @@
       if( i > 0 && visina[i] != visina[i-1] && zadnja[visina[i]] != -1 )
-         desno[zadnja[visina[i]]] = i;
+         desno[i] = zadnja[visina[i]]];

@@ -61,16 +61,17 @@
+ // cái toán tử <?= này ko nên dùng nữa.
   int rjesenje = inf;
+   for( int x = 0; x <= N; ++x ) a[1][x] = inf;
    for( int K = 0; K <= M; ++K ) {
      int k = K%2;
      int kplus1 = (K+1)%2;

-     for( int x = 0; x <= N; ++x ) a[kplus1][x] = inf;
      for( int x = 0; x < N; ++x ) {
         if( visina[x+1] == visina[x]+1 ) a[k][x+1] <?= a[k][x] + B;
         if( visina[x+1] == visina[x]   ) a[k][x+1] <?= a[k][x] + A;
         if( visina[x+1] == visina[x]-1 ) a[k][x+1] <?= a[k][x] + B;
-        if( desno[x] != -1 ) a[kplus1][desno[x]] <?= a[k][x] + C*(desno[x]-x);
+        if( desno[x] != -1 ) a[kplus1][desno[x]] <?= a[k][x] + C*(x-desno[x]);
      }
      rjesenje <?= a[k][N];
}

Không đơn giản đâu