Giải các bài toán tin bằng phương pháp quy hoạch động

ả

ằ

ươ

Ộ

Ạ

Gi

i các bài toán tin b ng ph

ng pháp QUY HO CH Đ NG

ư ể Có th  tóm l c nguyên lý QHĐ do Bellman phát bi u nh  sau:

ế ị ế ị ứ ụ ể ộ c th  i ph  thu c vào quy t đ nh Quy ho chạ   ở    các ở ướ  b

ướ ượ ộ đ ng là l p các bài toán mà quy t đ nh  ướ c đó b ớ ử c đã x  lý tr .

ậ

ạ

ể ả ằ

ươ

ộ

ạ

i b ng ph

ng pháp quy ho ch đ ng.

 Nh n d ng các bài toán có th  gi

ố ả ằ ươ ạ ộ i b ng ph ầ   ng pháp quy ho ch đ ng c n

M t bài toán P mu n gi ặ ể ộ có 2 đ c đi m sau:

ố ư

ừ ứ

i  u c a các bài toán con t ở ứ i  u cho bài toán con i  u Bellman, nghĩa là có   ấ   ấ  m c th p nh t ố   ơ  m c cao h n và cu i

ỏ ­ Bài toán P th a mãn nguyên lý t ả ố ư ủ ờ ể ử ụ i t th  s  d ng l i gi ầ ờ ả ố ư ể i t i gi đ  tìm d n l ả ố ư ờ i  u cho bài toán P. i t i gi cùng là l

­ Bài toán P có các bài toán con ph  ch ng lên nhau, nghĩa

ủ ồ ạ ạ ẹ là không gian bài toán con “h p” không t o d ng hình cây.

ướ ả ế ằ ươ ộ ạ

  Các b

c gi i quy t bài toán b ng ph ng pháp quy ho ch đ ng.

ướ ự ụ B c 1:Xây d ng hàm m c tiêu

ụ ố ư ủ Áp d ng nguyên lý t

ế

ấ ả ủ ụ ộ

ấ ướ ượ ự ụ ầ   i  u c a Bellman ta phân rã bài toán ban đ u ệ i quy t bài toán   ụ ể  ướ c đó. C  th ủ   ệ c hàm m c tiêu F(i) là nghi m c a ả c này là ta ph i xây d ng đ

ả thành các bài toán con có cùng c u trúc sao cho vi c gi ế con c p i ph  thu c vào k t qu  c a các bài toán con tr hóa b bài toán con c p i.ấ

ướ ị B ơ ở c 2: Xác đ nh các bài toán c  s .

ỏ

ể ế ơ ở ể ượ ặ ấ t ngay c k t qu  d  dàng. Đây chính là c  s  đ  tính

ế ấ ớ ệ ơ ở Bài toán c  s  là các bài toán con nh  nh t mà ta có th  bi ả ễ ả ế k t qu  ho c tính đ ơ nghi m cho các bài toán c p l n h n.

ướ ự ứ B ồ c 3: Xây d ng công th c truy h i

ứ ủ

ả ủ ố ứ ấ

ế ế ả ủ ự ấ ấ ụ Căn c  vào ý nghĩa c a hàm m c tiêu, tìm m i quan h  gi a các  ự bài toán con các c p, ta ti n hành xây d ng công th c tính k t qu  c a  bài toán c p i d a vào k t qu  c a các bài toán con c p tr ệ ử ế ướ c đó.

ướ ươ B ậ ả c 4: L p b ng ph ng án

ứ ệ

S  d ng công th c truy h i và nghi m các bài toán c  s  tính ữ ử ụ ấ ả ươ ả ồ ư t c  các bài toán con và l u tr  chúng vào b ng ph ơ ở ng án. ệ nghi m t

ướ ủ ệ ế ậ B c 5: K t lu n nghi m c a bài toán.

ự ả ươ ủ ỉ D a vào b ng ph ệ ng án ch  ra nghi m c a bài toán.

ướ ư Các b

ướ c b ể ế ầ ả c đ u làm quen ta cùng nhau gi ố   ừ ượ ẫ ng đ i ế   i quy t các bài toán

ấ ụ ể ả i quy t trên tuy r t c  th  nh ng v n tr u t c gi ướ ớ ọ v i h c sinh. Đ  các em b ả ơ đ n gi n sau:

ứ ố Bài toán 1: Tìm s  Fibonaci th  N?

ướ ụ B c 1: Hàm m c tiêu

ứ ố F(i) là s  fibonaci th  i.

ướ ơ ở B c 2: Các bài toán c  s

F(1) = 1; F(2) = 1

ướ ứ ồ B c 3: Công th c truy h i: F(i) = F(i­1) + F(i­2)

ướ ả ươ B c 4: B ng ph ng án

i F(i) 1 1 2 1 3 2 4 3 5 5 6 8 7 … … 13

ướ ệ B c 5: Nghi m F(N)

ể ố t. Bài toán 2: Di chuy n quân t

̀ ́ ư ̣

̀ ư ̣ ̣ ̣ ́ ́ ̀ ở  môt đên N. Ô năm ̀ ̀ ơ Cho môt ban c  kich th ́ ́ ̉ ượ c đanh sô t ́ ̀  trên xuông d ̀  hang i, côt j  goi la Ô(i, j). Ng ̀ ̀ ́ ́ ̣ ̣ ̣ ̉

́ ̀ ̣ ̉ ̉

̀ ́ ́ ́ ́ ́ ́ ́ ư ư ư ̉ ̣ ̣

́ ́ ́ ́ ̉ ́ ́ ̀ ́ ́ ươ ̣ ư ươ c NxN. Cac dong t    trai i, cac côt t ̀ ̀ ́ ̣   ươ qua phai đ i ta đăt ̀ ́ ơ   môt con tôt trăng tai Ô(1,1) va M con tôt đen trên cac ô con lai cua ban c  sao cho ̀ ́ ̀   không co 2 con tôt nao năm trên cung môt ô. Ta co thê di chuyên con tôt trăng sang ô ̃ ́ ́ ́ ươ   i ô đang ch a no nêu nh  ô đo không ch a tôt đen. Ban hay bên phai, hoăc xuông d ́ ́ ́ tinh xem co bao nhiêu cach di chuyên tôt trăng đên Ô(N, N).

ướ ụ B c 1: Hàm m c tiêu

ể ố ố ắ F(i, j) là s  cách di chuy n quân t ế t tr ng đ n O(i, j).

ướ ơ ở B c 2: Các bài toán c  s

j:1..N ;

F(0,j) = 0 (cid:0) F(i,0) = 0 (cid:0) i:1..N

ố ọ ộ (u, v) là t a đ  các quân t t đen

ướ ứ F(1,1) = 0; F(u, v) =0 (cid:0) ồ B c 3: Công th c truy h i

ấ O(i­1, j) và O(i, j­1) m i có th  đ  đ n đ

Ta th y ch  đ ng  ượ ố ể ể ế ộ ượ ớ ố ớ ế ằ ố ở c O(i, j). c O(i, j) b ng s  cách đ n O(i­1, j) c ng v i s  cách

ỉ ứ ế Do đó s  cách đ n đ ế đ n  O(i,j­1)

ượ Ta đ c:   F(i, j) = F (i­1, j) + F(i, j­1)

ướ ả ươ B c 4: B ng ph ng án

0 1 2 3 4 5 6 1 T 0 0 0 0 0 0 1 1 1 1 0 1 0 1

D

2 3 4 D D 3 9 9

5 0 1 1 4 20

6 D 0 1 2 0 42 0 1 2 0 1 0 1 3 3 4 0 1 0 3 7 1 1 1 1 2 6 0 1 1 2 2

ệ ả ạ ọ ờ ươ Minh h a hi n tr ng bàn c            B ng ph ng án

ướ ệ B c 5: Nghi m F(N, N) = 42

ầ ử ấ ỏ ề ệ Tìm dãy các ph n t là dãy con dài nh t th a mãn đi u ki n bài toán. D ng 1: ạ

ươ Ph

ụ

ơ ở

ứ ồ ớ ề ỏ ng pháp chung ộ + Hàm m c tiêu: F(i) là đ  dài dãy con + Bài toán c  s : F(1) = 1 + Công th c truy h i: F(i) = Max {1, F(j)+1 } v i A ệ   j và Ai th a đi u ki n

bài toán

ề ư ả ữ ng án: Dùng m ng 1 chi u l u tr .

ệ ươ ả + B ng ph + Nghi m bài toán: F(N)

ụ ậ Các bài t p áp d ng:

ươ Tên ch ng trình: ế Bài 1: X p Tháp Tower.Pas

ạ ườ ọ ỏ ỉ

ờ ờ M t l n n a, B m l ấ ể ệ ượ c mình không ch  là ng ấ i th  hi n đ ạ i h c gi ậ

ơ ế ấ ề ắ ạ ơ ớ ị

ộ ầ ữ ỏ Ở ớ cũng r t gi i.  ườ mình là ng ể ắ có th  th ng đ Ở ụ ứ ườ ớ ề ơ   i mà ch i ể ệ    l p B m, các b n đang r t thích ch i x p tháp và c u đang th  hi n ạ   ệ i vô đ ch trong trò ch i này khi th ng r t nhi u b n cùng l p. Li u b n ượ ờ c B m? ơ  trò ch i này, ng đ ng v i nhi u kích th c cho N hình tr

ườ ơ ượ i ch i đ ơ ế ượ i ch i x p đ c tòa tháp cao nh t t

ế ứ ự ừ t c x p khít v i kh i

ả ượ ế ườ ướ ấ ừ ớ ng kính đáy hình d ướ   c ụ    các hình tr  theo đúng ố ở ướ ườ   ng i, hay đ  d ể  ố ụ ộ i. M t kh i tr  có th

ứ ự đã cho.

ừ ầ khác nhau và yêu c u ng  1 đ n N sao cho kh i  th  t ủ kính đáy c a hình trên không v ư dùng ho c không dùng nh ng ph i đúng theo th  t  file D  li u:

ặ ữ ệ  Cho t ầ

ế ề ố ở  trên ph i đ ượ t quá đ ả Tower.Inp ố Dòng đ u ghi s  N (N≤ 1000000) ỗ N dòng ti p theo m i dòng ghi 2 s  R ố i và Hi là bán kính đáy và chi u cao

hình tr  th  i.

ụ ứ ế K t qu :

ấ ủ ộ ố ề ấ ớ ế ượ ả  Ghi ra file Tower.Out M t s  nguyên duy nh t là chi u cao l n nh t c a tòa tháp x p đ c.

Ví du:

Tower.Out 10

Tower.Inp 4 4  2

2  5 1  3 3  1

ề ấ ổ ớ Đây là bài toán tìm dãy con không tăng theo Ri có t ng chi u cao l n nh t.

ậ ướ Nh n xét:  ẫ H ng d n

ế ượ ớ ỉ ọ ấ ủ ố c v i kh i i là đ nh.

ộ ớ i:1..N;  ồ

G i F[i] là đ  cao l n nh t c a tòa tháp x p đ F[i] = H[i] (cid:0) ứ Công th c truy h i: ế ượ c trên kh i j (1≤ j < i) hay R[i] ≤ R[j].Ta đ c:

j:1..i­1. (cid:0) ệ ố ố ế ượ N u kh i i x p đ F[i] = Max{F[j]+H[i]} (cid:0) i:1..N Nghi m bài toán: Max{F[i]}

ố Bài 2: Dãy s  WAVIO: ố ầ ử ầ

ố ế Dãy s  Wavio là dãy s  nguyên th a mãn các tính ch t : các ph n t ầ ử ỉ ả ấ ỏ ầ  đ nh sau đó gi m d n. Ví d  dãy s

ụ ỉ ố ộ

ầ ộ ấ ừ ớ ồ  dãy đó .

ướ ắ    đ u s p ố 1 2 3 4  ế x p thành 1 dãy tăng d n đ n 1 ph n t 5 2 1 là 1 dãy Wavio đ  dài 7. Cho 1 dãy g m N s  nguyên, hãy ch  ra m t dãy con   ộ Wavio có  đ  dài l n nh t trích ra t ẫ   H ng d n:

1, A2,...Ai .  i, A2,...AN.

ộ ộ ả

ấ ủ ấ ủ ố ớ ớ ồ ứ

ệ ả ỏ ầ ủ L1[i] là đ  dài l n nh t c a 1 dãy con tăng d n c a dãy A ầ ủ L2[i] là đ  dài l n nh t c a 1 dãy con gi m d n c a dãy A ư Công th c truy h i gi ng nh  bài toán dãy con tăng. ầ ử Nghi m bài toán: Tìm ph n t j trong 2 m ng L1, L2 th a mãn L1[j]+L2[j]

ấ

­ ­ ­ ­ ớ l n nh t.

ố ứ ươ Tên ch ng trình: Bài 3: Xâu con đ i x ng Palin.Pas

ố ứ ọ ừ Xâu đ i x ng là xâu mà khi đ c t bên trái sang ph i hay ng c l

ố ứ ộ ượ ạ ề i đ u cho ướ c. Xâu

ộ ế ủ ộ ố

ự .

ộ ỏ ượ ằ c b ng cách b  đi m t s  kí t ộ ộ ố ượ ấ ộ ớ ả ấ ủ ự ủ  c a S. ộ ấ c ả  Palin.Out g m m t s  duy nh t là đ  dài l n nh t tìm đ

ả ạ m t k t qu . B n hãy tìm m t xâu con đ i x ng dài nh t c a m t xâu cho tr ộ con c a m t xâu S có đ ồ ữ ệ  Palin.Inp g m m t dòng duy nh t ghi xâu S có đ  dài không quá 10000 kí t ấ D  li u: ồ ế K t qu : Ví du:

Palin.Out

5

ướ Palin.Inp banana ẫ H ng d n

ấ ự

ứ ỉ ố ớ ố ứ ế th  i có t n t ạ G i F[i,len] là ch  s  j l n nh t sao cho j ≤ i và trong đo n xâu kí t ượ ộ i xâu con đ i x ng có đ  dài len. N u không tìm đ ế ự  j đ n kí t c j thì F[j, len]=0.

i:1..N

ỏ ơ ấ ớ ớ ự ứ ọ ồ ạ F[i, 1] = i (cid:0) ằ F[i, 2] b ng Max c a F[i­1, 2] và j v i j l n nh t nh  h n i  và kí t ằ    th  j b ng

ự ứ ủ ầ th  i trong xâu ban đ u.

ứ ồ kí t Công th c truy h i:

ự ế ọ i vào xâu đ i x ng.

ỏ ơ ố ứ ự ứ ự ứ ­ F[i, len] = F[i­1, len] n u không ch n kí t ấ ớ ­ F[i, len] = giá tri j l n nh t nh  h n F[i­1, len­2] và kí t ằ  th  j b ng kí t th  i.

ầ ử ạ D ng 2: Tìm dãy các ph n t ấ  là dãy con chung dài nh t

ươ Ph

1, A2,…, AM; B1, B2,…, BN (Các ph n t

ầ ử ủ ể c a dãy có th  là s ố

ặ ng pháp chung ả ử Gi ự s  cho 2 dãy A ầ ho c kí t ). Yêu c u tìm dãy con chung dài nh t c a hai dãy đã cho.

1,

ấ ủ ộ ấ ủ +Hàm m c tiêu: F(i, j) là đ  dài dãy con chung dài nh t c a hai dãy A

ụ A2,…, Ai; B1, B2,…, Bj. (cid:0) j:1..N i:1..M; (cid:0)

ơ ở ồ ứ ế + Các bài toán c  s :  F(0, j) = 0 = F(i, 0)  + Công th c truy h i: N u A[i]=B[j] thì F(i, j) = F(i­1, j­1) +1

c l

Ng ả i ề ể ư ươ ượ ạ F(I, j) = Max(F(i­1, j), F(i, j­1) ữ ng án: Dùng m ng hai chi u đ  l u tr .

ệ ả + B ng ph + Nghi m bài toán: F(M, N)

ụ ậ Các bài t p áp d ng:

Bài 1: Xâu con chung dài nh tấ

ủ ấ ộ ớ ủ Cho 2 xâu X,Y. Hãy tìm xâu con c a X và c a Y có  đ  dài l n nh t.

ướ ẫ H ng d n

ọ ồ ầ ủ ộ đ  dài xâu con chung dài nh t c a xâu X(i) g m i kí t ph n ­ G i L(i,j) là ự ầ  đ u c a X

ồ ầ ủ ph n (X(i)=X[1..i]) và xâu Y(j) g m j kí t (Y(j) =Y[1..j]). ấ ủ ự ầ  đ u c a Y

ơ ở ­ Bài toán c  s   L(0,j)=L(i,0)=0.

ồ ứ ­ Công th c truy h i

ế ế L(i,j) = L(i 1,j 1)+1 n u X[i] = Y[j].  L(i,j) = max(L(i 1,j), L(i,j 1)) n u X[i]≠Y[j].

ộ ươ Tên ch ng trình: ấ Bài 2: Dãy con chung b i hai dài nh t Lcs2x.Pas

ủ

ữ c b ng cách xóa b t m t s  ph n t ế ứ ự ủ  nguyên th  t

ượ ọ Dãy C = c1, c2, .. ck đ ớ i, nghĩa là tìm đ

c g i là dãy con c a dãy A = a1, a2, .., an n u C có th ộ ố c dãy các ch  s  1 ≤ l1 < l2 < …  ọ ộ ầ ử ủ ố ậ ượ ằ nh n đ ượ ạ ầ ử ph n t  còn l a_l1, c2 = a_l2, …, ck = a_lk. Ta g i đ  dài c a dãy là s  ph n t ể     c a các < lk ≤ n sao cho c1 =   c a dãy.

ủ ừ ủ ế

ộ ỏ ủ ề ệ ầ ử ủ  c a dãy A và gi ỉ ố ủ cượ   Cho hai dãy A = a1, a2, …, am và B = b1, b2, …, bn Dãy C = c1, c2, …, ck đ ừ ọ g i là dãy con chung b i hai c a dãy A và B n u C v a là dãy con c a dãy A, v a là   dãy con c a dãy B và th a mãn đi u ki n 2 × ci ≤ c(i+1) (i = 1, 2, …, k – 1).

Yêu c uầ

ộ ộ ộ ớ ấ   Cho hai dãy A và B. Hãy tìm đ  dài dãy con chung b i hai có đ  dài l n nh t

ủ c a hai dãy A và B.

Input

(Lcs2x.Inp) ứ ầ ố ượ ỗ   ế ng b  d  li u. Ti p đ n là T nhóm dòng, m i

ộ ữ ệ ạ

ươ ố ng m và n.

ỗ ố ầ ứ ượ ứ ố ế Dòng đ u tiên ch a T là s  l ề ộ ộ ữ ệ nhóm cho thông tin v  m t b  d  li u theo khuôn d ng sau: (cid:0) Dòng đ u ch a 2 s  nguyên d ứ (cid:0) Dòng th  hai ch a m s  nguyên không âm a1, a2, ..., am m i s  không v t quá

109.

(cid:0) Dòng th  ba ch a n s  nguyên không âm b1, b2, ..., bn m i s  không v

ỗ ố ứ ứ ố ượ t quá

(cid:0) ượ ộ ấ ấ ố ộ c ghi cách nhau ít nh t m t d u cách. 109. Các s  trên cùng m t dòng đ

ớ ạ Gi i h n (cid:0) ố 30% s  test có m, n <= 15.

(cid:0) ố (cid:0) ạ 30% s  test khác có m, n <= 150. ố có 40% s  test còn l i có m, n <= 1500.

Output

ộ ộ Ghi ra T dòng, m i dòng ghi m t s  nguyên là đ  dài dãy con chung b i hai dài

ộ ố ớ ộ ữ ệ ấ ủ (Lcs2x.Out) ỗ ươ ứ ng  ng v i b  d  li u vào. nh t c a dãy A và B t

ướ ẫ Example Lcs2x.Inp 1 5 5 5 1 6 10 20 1 8 6 10 20 Lcs2x.Out 3 H ng d n:

ọ ộ ấ ủ ỏ

ề ề

ồ

G i F[i, j] là đ  dài dãy con chung dài nh t c a dãy A[1..i] và dãy B[1..j] th a  ệ đi u ki n đ  bài và A[i]=B[j]. ứ Công th c truy h i:  ế thì  F[i, j]=0

ề ệ ề ­ N u A[i]<>B[j] ­ F[i, j]= Max{F[u, v]/ u

ỉ ố ồ ạ   ỏ i 2 ch  s  k, t sao cho Max{F[u, v]/ u

ầ ử ỏ ồ ệ ạ D ng 3: Tìm dãy g m các ph n t ề  th a mãn đi u ki n nào đó

ươ Ph

ạ ả ử ng pháp chung Gi có “kh i l

1, B2, 1, A2,…, AN và “giá tr ” là B ộ ng” ph  thu c M

s  có N lo i ph n t ọ ố ượ ị ụ có “kh i l

ị ạ ượ ố ượ ng” là A ạ ng các lo i ph n t ấ ấ ỏ ầ ử ộ ố ượ ầ …, BN . Yêu c u ch  ra m t s  l ể đ  giá tr  đ t đ

ụ ầ ử ượ ọ đ ố   ể ổ c ch n đ  t ng “kh i

ề ị  là i th a đi u ki n bài toán. ng” các ph n t ượ l

ồ ầ ử ặ ớ ể c là nh  nh t ho c l n nh t có th . ổ +Hàm m c tiêu: F(i) là t ng giá tr  các ph n t ệ ỏ ầ ử ơ ở + Bài toán c  s : F(0) = 0  ứ + Công th c truy h i:

ớ

F(k) = Max{F(k­Ai)}+Bi v i k:1..S  ầ ủ ể

ể ư ươ ề ả

ệ ề ệ ộ (Tùy thu c vào yêu c u c a bài toán, có th  là Min) ữ ộ ả ng án: Dùng m ng m t chi u đ  l u tr . + B ng ph ỏ ớ + Nghi m bài toán: F(k) v i k th a đi u ki n bài toán.

ụ ậ Các bài t p áp d ng:

ươ

Bài 1: MONSTER ờ ầ ng trình ướ ộ ộ B m ph i đi qua m t thung lũng đ y c : Monster.Pas p có m t ch  s  th

Tên ch ướ ứ ộ ụ ể ộ ố

ướ ể ố

ồ ứ ẽ

ướ ặ ộ

ủ ệ ữ ủ ố ộ ộ

ộ

ữ ỏ ơ ộ ộ ả ướ ệ ự ữ ứ hi n s  hung d . C  th  tên c ơ ị ọ ướ ấ ứ ờ c nguy c  b  b n c B m đ ng tr ể ộ ố ộ ữ nh ng đ ng vàng c a mình đ  mua chu c m t s  tên c ờ ể ả ồ đ ng vàng đ  b o v  cho B m. Khi g p m t tên c ờ ổ t ng đ  hung d  c a s  tên c ắ ờ ể ồ ạ B m. Nói các khác đ  t n t ướ ặ ườ i khi g p m t tên c tr ỉ ố ể  ỗ p. M i tên c ữ p th  i có m c đ  hung d  là m t s  nguyên H[i].   ằ   ờ p t n công, tuy nhiên B m ta có th  s ng sót b ng ướ ướ p th  i s  đòi T[i] p. Tên c   ơ   ữ ớ ộ ế p, n u nó có đ  hung d  l n h n ẽ ấ ướ ướ   p đó s  t n công p mà B m đã mua chu c thì tên c ướ ả ờ p này. Trong   i B m b t bu c ph i mua chu c tên c ộ  ổ ặ ằ ộ pcó đ  hung d  nh  h n ho c b ng t ng đ ợ ng h p ng ượ ạ c l

ướ ờ ể ấ ờ ộ p mà B m đã mua chu c thì nó không th  t n công B m và

ặ

ờ ạ ả ố ờ ể ượ ượ ữ ủ ố hung d  c a s  tên c ộ ể B m có th  mua chu c nó ho c không. ấ B n hãy tính s  vàng ít nh t mà B m ph i dùng đ  v t qua đ c thung lũng.

Input: Monster.inp

ố ờ

1, T2, …, TN. (Ti<10)

ầ ứ ứ ố ố ng N (N<1000) và V (V<10000) là s  vàng B m có. 1, H2, …, HN. (Hi<109) ươ ươ ố Dòng đ u ghi s  nguyên d Dòng th  2 ghi N s  nguyên H Dòng th  3 ghi N s  nguyên d ng T

Output: Monster.out

ử ụ ế ượ ố ượ ấ ờ Ghi ra s  vàng ít nh t B m s  d ng n u v t qua đ c thung lũng,ng ượ ạ c l i

ghi ­1

Ví dụ:

Monster.out

Monster.in p

2

3  5 8  5  10 1  1  2

ướ ẫ ả H ng d n gi i bài MONSTER

ấ ủ ữ ớ ụ ổ

ướ ­ Hàm m c tiêu: G i F[i, j] là t ng đ  hung d  l n nh t c a các tên c ề ầ ộ ồ ờ   p mà B m ế   p đ u tiên và dùng j đ ng ti n vàng. N u

ờ ộ ọ ướ c khi đi qua i tên c ầ ướ ớ ồ p đ u tiên v i j đ ng vàng thì F[i, j] = ­1.

ượ mua chu c đ ể B m không th  đi qua i tên c ơ ở ­ Các bài toán c  s :

ượ ạ c l i F[1, j] = ­1.

ế F[1, j] = H[1] n u j ≥ T[1]  ng ứ ồ

ướ ộ ờ ­ Công th c truy h i: (i > 1) B m mua chu c tên c ứ p th  i thì

F[i, j] = F[i­1, j­T[i]]+H[i] (đi u ki n: F[i­1, j­T[i]] ≠ ­1)

ờ ộ

B m không mua chu c tên c ề ề ệ ứ ướ p th  i thì  ệ

ế ệ ặ F[i, j] = F[i­1, j] (đi u ki n: F[i­1, j] ≥ H[i]) ỏ ủ ấ ­ Nghi m c a bài toán là j nh  nh t sao cho F[n, j] <> ­1 ho c F[n,v] n u F[n,v]=

­1.

ề ệ ươ Tên ch ng trình:

ệ ố Bài 2: H  th ng ti n t Money.Pas

ộ ệ ố

ị ườ ị ủ ồ ơ ị ữ   ề ệ ấ  r t riêng. Đó là giá tr  c a nh ng   ng các đ ng xu có các giá tr  nh , 5, 10, 20 đ n v , đôi khi đ ng xu 2

ố ơ t h n.

ể ố ể ấ ể Chúng ta hãy cùng theo dõi m t h  th ng ti n t ồ ứ ườ c dùng đ  đo l ế i đ u mu n bi ng t t có bao nhiêu cách khác nhau đ  có th  l y ra m t l

ụ ề ề

ệ ố ề ệ ố ị ư ồ ơ

ướ ằ ể ấ ị ơ

ộ ượ ế ề ng ti n S hãy cho bi t có bao

ấ ượ ố ề ừ ệ ố ồ đ ng xu. Thông th ượ ị ơ đ n v  cũng đ ộ ượ   ườ ề ọ ng M i ng c b ng cách dùng các h  th ng ti n xu khác nhau. Ví d  dùng h  th ng [1, 2, ti n cho tr ơ   …,18] có th  l y ra 18 đ ng b ng nhi u cách khác nhau nh : 1 xu 18 đ n v , 2 xu 9 đ n ơ ị ề v , 2 xu 8 đ n v  và 2 xu 1 đ n v ,… và nhi u cách khác. Yêu c u:ầ  V i h  th ng ti n xu cho tr ớ ệ ố c s  ti n S t ằ ị ướ ề c và m t l ề  h  th ng ti n xu đã có. nhiêu cách l y đ

ữ ệ  Cho t file D  li u:

ề ệ ạ ố ố ố ­ Dòng   đ u   ghi   hai   s   N   (1

ươ ệ ố ề ệ ệ ừ Money.Inp ầ (S<10000) ứ ố ­ Dòng th  hai ghi N s  nguyên d ng là các m nh giá trong h  th ng ti n t .

ế K t qu :

ả  Ghi ra file Money.Out ố ộ ố ấ ượ Ghi ra m t s  duy nh t là s  cách tìm đ c.

Ví du:

Money.Out 10

Money.Inp 3  10 1  2  5

ẫ

ố ạ ượ ố ề ầ ồ i đ ng xu đ u tiên.

ừ c s  ti n là j t i:1..N; F[0,0]=0

ướ H ng d n ọ ­ G i F[i, j] là s  cách t o đ ­ F[0, j]=0 (cid:0) j:1..S; F[i, 0]=1 (cid:0) ồ ứ Công th c truy h i:

ử ụ ứ ế

ứ ồ ồ F[i, j] = F[i­1, j]  N u không s  d ng đ ng xu th  i. ấ ế ử ụ F[i, j] = F[i­1, j] + F[i­1, j­A[i]] N u s  d ng ít nh t 1 đ ng xu th  i. (j>A[i])

ị ươ Tên ch ng trình: Bài 3: Du l ch vòng quanh th  gi ế ớ i Travel.Pas

ế ớ ủ ị Trên tuy n đ ng c a xe ch  khách du l ch vòng quanh th  gi i xu t phát t

ườ ạ ứ ự ườ ế ấ ở  1 đ n N theo th  t

ệ ạ ủ ố

ả ừ ể ấ ế ố ừ ế b n X có N khách s n đánh s  t ể ị ạ trong đó khách s n N là đ a đi m cu i cùng c a hành trình mà t ị ph i d ng. Khách s n i cách đ a đi m xu t phát A ừ  ấ ế ng,  xu t hi n trên tuy n đ   ộ   ế ắ i đó tài x  b t bu c i Km (i=1, 2, …, N); A1

ẻ ể ả

ạ ả ứ ượ ừ

ượ

ả ị ế

ủ Đ  đ m b o s c kho  cho khách hàng, theo tính toán c a các nhà chuyên môn,   ế   ạ ỉ ở ạ  khách s n. Vì th , i cho khách ngh   ả   c Q Km  thì lái xe ph i  khách s n sau khi đã đi đ 2 . Đ  đ m b o l ch trình tài x  không đ ượ ừ   c d ng ạ ạ ể ả ộ ạ i m t khách s n nào đó.

ể ế ạ

ố ượ ả ả ủ ạ ứ ạ ạ sau khi đã ch y đ ạ ừ ế n u xe d ng l ả ộ ượ tr  m t l ư khi ch a ch y đ  P Km và ph i d ng t ộ   ắ ớ Ví D  : V i N=4, P=300, A1=250, A2=310, A3=550, A4=590. Xe b t bu c ườ  khách s n 4 là đ a đi m cu i cùng c a hành trình. N u trên đ   ng đi 2+((590­ ạ ạ ng ph t ph i tr  là : (310­300) i t ị i khách s n th  2 thì l

c P (Km) xe nên d ng l ỉ ở i cho khách ngh   ạ ề ng ti n ph t là : (Q­P) ả ừ ạ ủ ụ ạ ở ả ừ ph i d ng l i  ỉ ừ lái xe ch  d ng l 310)­300)2=500

ế

ượ ạ ầ ừ   ng đ n khách s n N, xe c n d ng ả ả ấ ỏ ạ l i ngh ế ườ ạ ng ph t mà lái xe ph i tr  là nh  nh t.

ừ ữ ệ   Vào t Yêu C u:ầ   Hãy xác đ nh  xem trên tuy n đ ị ỉ ở ữ D  Li u:

1, A2, A3, ..., An.

ố ng N (N<=10000); ng P (P<=500); ươ ể ổ ạ  nh ng khách s n nào đ  t ng l Travel.Inp   File  ươ ứ ố ầ Dòng đ u tiên ch a s  nguyên d ứ ươ ứ ố Dòng th  hai ch a s  nguyên d ứ ứ Dòng th  ba ch a các s  nguyên d ng A

( Ai<=2000000, i=1,2,..N)

ế K t Qu :

ạ ng ph t mà lái xe ph i tr  ;

ả  Ghi ra File Travel.Out ầ ứ ả ả ầ ượ ố ừ ạ ạ Dòng đ u tiên ghi Z là l Dòng th  hai ghi K là s  khách s n mà lái xe c n d ng l i cho

khách ngh ;ỉ

ừ ạ ạ Dòng th  ba ch  ch a ch  s  c a K khách s n mà xe d ng l i cho

ấ ỉ ỉ ứ ả ỉ ố ủ ạ ế ứ ứ khách ngh .(Trong đó nh t thi t ph i có khách s n th  N)

Ví D :ụ

Travel.Inp               4   300 250 310 550 590 Travel.Out 500   2 2 4

ướ ẫ ­ Hàm m c tiêu:

ượ ấ ế ạ ườ ừ ạ ị ể ng ph t ít nh t n u ng i lái xe d ng l i đ a đi m i.

H ng D n  ụ G i F[i] là l ơ ở

ồ

ọ ­ Bài toán c  s : F[0]=oo ứ ­ Công th c truy h i:  F[i]:=Min{F[j]+sqr(A[i]­A[j]­P)}; (cid:0) j=0,..i­1

ạ ặ D ng 4: Ghép c p

ươ Ph

ng pháp chung Gi

ả ử ế ượ c đánh ị c giá tr  V[i, j].

ầ ử ầ ử ị ượ c đánh s  t , dãy 1 đ ầ ử ớ  i dãy 1 v i ph n t ấ ượ  j c a dãy 2 đ ấ ớ ỏ s  cho hai dãy ph n t ố ừ s  t  1 đ n N. Khi ghép ph n t Tìm cách ghép sau cho t ng giá tr  thu đ

ố ừ ộ ế  m t đ n K, dãy 2 đ ủ ặ ượ ừ c là l n nh t ho c nh  nh t. c khi ghép t + Hàm m c tiêu: F(i, j) là t ng giá tr  thu đ i ph n t ầ ử ầ    đ u

ị ệ ề ớ ủ c a dãy 1 v i j ph n t

ượ ổ ỏ F(0, j) = 0 = F(i, 0)

ổ ụ ầ ử ầ ủ  đ u c a dãy 2 th a đi u ki n bài toán. ơ ở + Các bài toán c  s : ồ ứ + Công th c truy h i:

F(i, j) = Max{F(i­1, j­1)+v[i, j]; F(i, j­1; F(i­1, j)}

ươ ữ ể l u tr .

ề ề ệ ỏ ư ả ả ng án: Dùng m ng hai chi u đ   + B ng ph ệ ớ + Nghi m bài toán: F(K,N) v i k th a đi u ki n bài toán.

ụ ậ Các bài t p áp d ng:

ố ể ươ Tên ch ng trình: Bài 1: N i Đi m (Wires) Wires.Pas

ờ ườ ỗ ườ

ừ ượ ườ ế  1 đ n N, t ẳ ng th ng L1 đ

ừ ể ể ể ườ ng th ng L2 đ ố ừ c đánh s  b i P[1], P[2],..., P[N] cũng t ấ   ng N i ta đánh d u trên m i đ ả  trái qua ph i, còn các   ả    trái qua ph i,

ố ở ị ủ Trên Hai đu ng th ng song song L1 và L2, ng ẳ c đánh s  t đi m. Các đi m trên đ ượ ẳ đi m trên đ ộ trong đó P[1], P[2],.., P[N] là m t hoán v  c a các s  1, 2,..., N.

ể ể ố

ườ ọ ẳ ố ệ 2 đ

ố ượ ấ ớ ệ ề ề ể ạ ặ ố   c nhi u c p đi m nh t v i đi u ki n các đo n n i

không đ

File

ươ ng  N (N<=10000)

ố ố ệ ủ ố Ta g i các s  gán cho các đi m là s  hi u c a chúng. Cho phép n i hai đi m trên ng th ng có cùng s  hi u. Yêu C u:ầ  Tìm cách n i đ ượ ắ c c t nhau .  ữ ệ  Vào t ừ D  Li u: ầ ứ Wires.Inp ứ ố ứ ­ Dòng đ u tiên ch a s  nguyên d ­ Dòng th  hai ch a các s  P[1], P[2],....,P[N]

ế K t Qu :

ứ ố ượ ạ ố ng đo n n i tìm đ

ố ượ ố ệ ủ c. ủ ứ ầ ạ ố ả  Ghi Ra File Wires.Out  ­ Dòng đ u ch a s  K là s  l ­ Dòng ti p theo ch a K s  hi u c a các đ u mút c a các đo n n i đ ố ượ   c

ầ ế ầ  tăng d n. ghi theo th  t

ứ ự Ví D  :ụ

WIRES.INP

9 WIRES.OUT 5

2 5 3 8 7 4 6 9 1 2 3 4 6 9

ướ ẫ H ng d n:

ạ ẳ ọ ố ố ố ủ ủ ể ặ ­ Hàm m c tiêu: G i F(i) là s  đo n th ng t i đa c a các c p n i c a các đi m t ừ

ụ 1 đ n i.ế

ơ ở ­ Các bài toán c  s : F[0]=0; ứ ồ ­ Công th c truy h i: F[i] = Max{F[P[j]]+1} (cid:0) j:=1..ViTri(i) trong dãy P[1], P[2],.., P[N].

ệ ­     Nghi m bài toán: F[N].

ươ Tên ch ng trình:

Bài 2  Công trình Congtrinh.Pas

ầ ơ

ầ ấ ừ ượ ể ị ậ ệ Có N công trình c n v t li u thi công. Công trình i c n cung c p D[i] đ n v  hai kho A và B. C c v n chuy n m t đ n v  hàng t c cung c p t

ướ ể ướ ị ườ ấ ộ ơ ừ ng i là A[i]. C c v n chuy n m t đ n v  hàng t

ậ ị ậ ộ ơ ố ơ ủ

ế ườ ườ ừ ế ố ị  ừ  ế    kho B đ n ừ ủ    ng sao

ổ t kho A có R đ n v  hàng và t ng s  hàng c a hai kho v a đ ng. Hãy phân ph i hàng t  hai kho đ n các công tr ấ ể ậ

hàng. Hàng đ ế kho A đ n công tr ườ ng i là B[i]. Bi công tr ấ cung c p cho N công tr ướ ổ cho t ng c ữ ệ  cho t D  li u

ứ c phí v n chuy n là ít nh t. ừ ầ

ứ ứ ứ

K t quế

ấ ổ ể file “congtrinh.inp” ố Dòng đ u ch a 2 s  N R  (N,R <1000) ố Dòng 2 ch a N s  D[1] D[2]…D[N] ố Dòng 3 ch a N s  A[1] A[2]…A[N] ố Dòng 4 ch a N s  B[1] B[2]…B[N] ả xu t ra file “Congtrinh.out” ấ ậ Ghi t ng chi phí v n chuy n ít nh t

Ví dụ:

Congtrinh.inp

Congtrinh.out  1070

H ng d n

ườ ướ ấ ợ ướ ­ c phí v n chuy n nh  nh t trong tr ng h p kho A

5100 30 80  80  50  40 3 5    10  4    23 4 6    2    7    4 ẫ Hàm m c tiêu: S(i ,j) là c ị

ế ấ ậ ườ cung c p j đ n v  hàng đ n các công tr ỏ ể ng 1..i. (j ≤ R)

ồ ­

ố ơ ậ ớ ị ụ ơ ứ Công th c truy h i: ấ   Nh n xét: S(1,j) = Min {A[1]*x + B[1]*(D[1]­x) } v i x là s  đ n v  hàng cung c p

ừ t kho A  (x ≤ D[1] và x ≤ j)

Do đó  S(i, j) = Min {A[i]*x + B[i]*(D[i]­x) + S(i­1, j­x)}

ắ Bài toán 3. C m hoa

ị ẩ ỗ c đ t tr

ọ ế ớ ề ố ệ ệ ỹ

ầ ắ ẳ ạ ố C n c m k bó hoa khác lo i nhau vào n l  x p th ng hàng sao cho hoa có s   ạ ỏ ượ ặ ướ ế ố ệ ớ t giá tr  th m  c hoa có s  hi u l n. V i m i lo i hoa i ta bi hi u nh  đ ượ ố ự ọ ắ c ghi cách   nhiên và đ  Các s  li u đ u là s  t  j, v[i,j]. m  khi c m hoa đó vào l ỗ ở ấ nhau b i d u cách trên m i dòng.

ầ ị

ệ ị ở ả ớ dòng th  hai tr  đi là các giá tr  v[i,j] v i i:=1..k và j:=1..n; 1 <= k <= n <= 100.

ầ ả ồ ừ ữ ệ D  li u vào ghi trong t p văn b n HOA.INP: dòng đ u tiên là hai tr  k và n. T   ứ ữ ệ D  li u ra ghi trong t p văn b n HOA.OUT g m hai dòng: dòng đ u tiên là

ố ư ố ệ ứ ừ ắ ng án c m hoa t i  u. T  dòng th  hai là dãy k s  hi u

ị ẩ ọ ỹ ủ ỗ ệ ươ c ch n cho m i bó hoa. ổ t ng giá tr  th m m  c a ph ọ ượ  đ l

Thí dụ:

ạ ị ườ D ng 5: Xác đ nh đ ấ ắ ng đi ng n nh t

ươ Ph

ố ử ố ộ ng pháp chung Gi ng đi gi a hai thành ph  i, j là A[i, j]. Tìm

ấ ả ử ắ ườ đ

ử ụ ườ ấ ừ ắ ng đi ng n nh t t ế  i đ n j.

ồ

ề

ể ư ấ ệ ắ (cid:0) k:1..N ữ ử ố ườ  s  có N thành ph , đ  dài đ ố ấ ỳ ng đi ng n nh t gi a hai thành ph  b t k . ộ + Hàm m c tiêu: F(i, j) là đ  dài đ ơ ở + Bài toán c  s : F(i, i) = 0 ứ + Công th c truy h i: F(i, j) = Min{F(i, k)+F(k, j)}  ả ươ ả ng án: Dùng m ng hai chi u đ  l u tr + B ng ph ườ + Nghi m bài toán: F(u,v) là đ ng đi ng n nh t gi a 2 tph  u, v

ụ ậ Các bài t p áp d ng:

ể

ộ ế ườ ừ ố i mu n đi t hình tròn này sang

ố ừ ướ

1 đ n N). M t ng c: ể ấ ủ ữ ầ ­ N u kho ng cách gi a 2 đi m g n nh t c a 2 hình tròn không quá 50 cm thì

có th  b

ể ả

ượ ể

ợ ọ ố Bài 1: Di chuy n trên các hình tròn  Cho N hình tròn (đánh s  t ầ hình tròn khác c n tuân theo qui  ả c sang. ả ơ ợ ng h p khác không th  sang đ ừ ng đi t c.  hình tròn này sang hình tròn khác đu c g i là càng "t

ế ể ướ ế ­ N u kho ng cách này h n 50cm và không quá 80cm thì có th  nh y sang. ườ ­ Các tr ộ ườ M t đ ả ả ườ ườ ằ ả ng đi có s  l n nh y b ng nhau thì đ ế ố  t" n u s   ng đi nào có

ườ ng đi đó "t ố ầ ơ ố t" h n.

ơ ượ ứ ộ ầ l n ph i nh y là càng ít. Hai đ ố s  hình tròn đi qua ít h n thì đ Các hình tròn đ ả c cho trong m t file văn b n, trong đó dòng th  i mô t

ả ộ ớ ồ ộ ộ

ị hình ố ự tròn s  hi u i (i = 1, 2,..., N) bao g m 3 s  th c: hoành đ  tâm, tung đ  tâm, đ  l n bán kính (đ n v  đo b ng mét).

ừ ố ệ ơ L p trình đ c các hình tròn t ả  m t file văn b n (tên file vào t

ừ ế

ườ ế ấ ố ằ ọ ọ ố ệ ẽ ư bàn phím), sau đó  bàn phím,   ặ   t nh t" theo nghĩa đã nêu (ho c ng trình s  đ a ra đ ng đi t

ừ ộ ậ ứ ỗ ầ ấ c  m i l n đ c s  hi u hình tròn xu t phát S và hình tròn k t thúc T t ừ ươ  S đ n T là "t ch thông báo là không có).

ầ ườ ượ ộ Yêu c u đ ng đi đ t d i d ng m t dãy các s  hi u hình tròn l n l

ố ệ ố ướ ả ổ ầ ượ   t   c nh y, t ng s  các hình tròn đi qua và

ế ướ ạ c vi ố ổ c đi qua trong đó nói rõ t ng s  các b ướ ầ ả ả c nào c n ph i nh y.

ố ọ ừ ứ ự

ầ ượ c n đ ữ nh ng b Bài 2: Mua vé Có N ng ụ

ế i th  i là T[i]. M i ng ườ ườ ứ ậ trong hàng.  1 đ n N theo th  t ườ ầ ỗ ư   i c n mua 1 vé nh ng ướ   ườ ứ ờ ể i có th  nh  ng c i đ ng ngay tr ờ   i th  i+1 thì th i gian mua vé cho 2

ấ ớ ờ i đ u có vé v i th i gian ít nh t. ứ ng án sao cho N ng

ườ ế i x p hàng mua vé. Ta đánh s  h  t ườ ụ ứ ờ Th i gian ph c v  bán vé cho ng ố ế ộ ố ề ượ c quy n mua t đ ườ ộ mình mua h . Ng ườ ng i là R[i], tìm ph ữ ệ  vào t D  li u

ố ố

i đa 2 vé, vì th  m t s  ng i th  i nh n mua vé cho ng ươ ườ ề ừ  file “Tick.inp” ứ ấ ứ ứ

K t quế

ổ ụ ụ

ế ỏ ầ ờ Dòng th  nh t ghi s  N (1

ỏ ố

ụ ụ ấ ể ờ ờ ướ ­ ườ ừ i t ng ườ   i

­

ụ ế ườ ụ mua vé thì th i gian ít nh t ph c v  k ng

i k t ứ ấ ộ ờ ứ ườ ờ ờ ườ ự i th  k nh  ng i là   ấ   i th  k­1 mua h  thì th i gian ít nh t

ầ ế ai r i kh i hàng thì ghi s  0). ẫ : H ng d n ụ Hàm m c tiêu: F(k) là th i gian ít nh t đ  ph c v  vé cho k ng ế ườ 1 đ n ng i k. ồ ứ Công th c truy h i: ấ Ta th y n u ng ế ườ ườ ụ ụ T[k]+F(k­1), n u ng ph c v  k ng i là R[k­1]+F(k­2)

Do đó: F(k) = Min( T[k]+F(k­1); R[k­1]+F(k­2))

ả ụ ụ ữ ờ ấ ­

i ng

ự ế ả ả ­ ả

ư ổ ứ ữ ệ T  ch c d  li u: M ng L[1..N], L[i] l u tr  th i gian ít nh t ph c v  vé cho i.ườ ự Sau khi xây d ng xong m ng L, d a vào 3 m ng L, T, R ta tìm ra k t qu ả ữ ậ ầ i nào c n mua vé ghi vào m ng KQ theo nh n xét:

ườ i k mua vé (KQ[k]=1) ng ượ ạ   i c l

N u T[k]+L[k­1]≤R[k­1]+L[k­2] thì ng ườ ườ nh ng ng ế i k­1 mua vé (KQ[k­1]=1). thì ng

ạ D ng 6: Di chuy n ể

ươ Ph

ố ớ ụ ệ ầ ạ ị

ể ị

ậ ặ ườ ứ ự ụ ệ ồ

ng pháp chung ể   Đ i v i các bài toán có d ng di chuy n thì vi c xác đ nh hàm m c tiêu c n căn ạ   ả ầ ứ c  vào quy lu t di chuy n cho phép và c n ph i chú ý vào giá tr  biên. Đây là d ng toán th   ng g p tuy nhiên vi c xây d ng hàm m c tiêu và công th c truy h i là khá ễ d  dàng.

ụ ậ Các bài t p áp d ng:

ươ Tên ch ng trình XYZ.PAS Bài 1:  KHU VUI CH IƠ

ả ậ ướ ộ B n đ  khu vui ch i là m t hình ch  nh t có kích th

ơ ặ ạ ỗ i ô (1, 1) và m t c ng ra đ t t i ô (M, N). M i ô (i, j) đ

ộ ể ỗ

ạ ể ế ị ỉ ờ ướ ặ ả

ơ ờ ặ ạ ấ ơ

ấ ị ộ ế ạ ờ t ph i đi theo l

ố ề ố ả ờ ạ ấ

ề c trò ch i mình thích và ít t n ti n nh t. B n hãy giúp B m nhé. ừ ữ ồ ơ c MxN ô vuông. Khu vui   ượ ố  ộ ổ ặ ạ ộ ổ c b ch i có m t c ng vào đ t t ạ ơ   trí m t trò ch i, giá vé vào ô (i, j) là C[i, j]. T i m i ô khách có th  di chuy n sang các ô i. Vào ngày ngh , B m quy t đ nh tham quan khu vui chung c nh bên ph i ho c phía d   ơ ờ   ộ ch i. Trong khu vui ch i có m t trò ch i B m r t thích đ t t i ô (U, V) và nh t đ nh B m ư ả ph i tham gia trò ch i này. Nh ng s  ti n có h n B m không bi    trình nào ơ ượ ể đ   ch i đ D  li uữ ệ  cho t

(cid:0) ơ ơ  file XYZ.INP ầ ố N) 10000 ; 1(cid:0) M ; 1 (cid:0)

ế ỗ U(cid:0) ậ V (cid:0) ớ ­ Dòng đ u là 4 s  M, N, U, V ( 3 ≤ M, N  ố ể ệ ­ M dòng ti p theo, m i dòng ghi N s  th  hi n ma tr n chi phí C, v i C[i, j] là giá

ộ ố ấ ấ ượ c. vé khi vào ô (i, j). K t quế

ả ghi ra file XYZ.OUT m t s  duy nh t là chi phí ít nh t tìm đ Ví d :ụ

XYZ.OUT 25

XYZ.INP  4  5  2  3 5  6  4  4  1 1  2  9  1  5 1  1  1  2  3 4  6  5  1  4

ướ ẫ H ng d n

ọ ấ ế

ứ

ồ ả ả ắ ­ G i F(i, j) là chi phí ít nh t khi đ n Ô(i, j) ­ Công th c truy h i: F(i, j) = Min{ F(i, j­1), F(i­1, j)}+A[i] ấ   ế ­ Do b t bu c ph i qua Ô(U,V) nên k t qu  bài toán chính là t ng chi phí th p

ế ấ ấ ừ ừ ộ  Ô(1,1) đ n Ô(u,v) và chi phí th p nh t đi t ổ ế  Ô(u,v) đ n Ô(m,n). ấ nh t đi t

ươ Tên ch ng trình: Bài 2: NH YẢ Jump.Pas

ượ ấ ẵ ụ ọ ộ ị ị c đánh d u s n, v  trí i có t a đ  X ọ ộ i . Xét m tộ

Trên tr c t a đ  Ox có N v  trí đ ơ

ể ủ ử ướ

ệ ọ

ặ ượ ạ c l

ả trò ch i nh  sau: ụ ắ ầ ả ề ớ

ả ướ ệ ơ ấ ng và l n h n ho c b ng b c nh y li n tr

ạ ẽ ự ả ơ ạ ề ề ặ ể ự ả ằ ệ ề ả ạ

ủ ạ ố ể ể ạ ổ ư ệ ả   c nh y gi a các đi m đã đánh ị ắ ầ ộ c khi b t đ u trò ch i b n ph i ch n đi m b t đ u (là m t trong N v  trí đã   ệ   ự ạ ượ c th c hi n i. B n đ ả   ướ ộ c nh y ướ ớ   ả c. T t nhiên v i ộ ố  ỗ ị ướ c nh y. M i v  trí i có m t s ồ   ế ượ ị c (bao g m i, đi m c a b n là t ng s  đi m các v  trí b n đ n đ

ể ạ ượ ố ể ấ ớ c s  đi m l n nh t.

ữ ệ   Vào t

File  ố ươ ầ

i, Pi. (1

ng N (1

Pi<106)

ế K t Qu :

ả  Ghi ra File Jump.Out ố ể ộ ố ấ ạ ượ ấ ớ M t s  duy nh t là s  đi m l n nh t đ t đ c.

Jump.Out 25

Ví D :ụ            Jump.Inp 6 5  6 1  1 10  5 7  6 4  8 8  10

ả ị ươ ứ ậ ượ Gi ả i thích: Các v  trí nh y qua: 4  5  7  10 (t ể ng  ng đi m nh n đ c: 8+6+6+5=25)

ướ

ẫ H ng D n  ể ơ ể ả ị Đ  đ n gi n ta có th  xem nh  các v  trí đã đ

i.  c s p x p tăng d n theo X   c làm

ỉ ư ề ầ ể ượ ế ượ ạ c l i có th  đ

ả ấ ọ ộ i và th  t

ạ ượ ớ ấ ố ị ượ ắ ả ệ i tăng, vi c nh y ng ị ứ ự  các v  trí. ị ể ế c l n nh t có th  n u v  trí cu i cùng là v  trí j và

ng t ­ G i F[i, j] là s  đi m đ t đ ướ

ướ ệ Ngoài ra ta ch  xét vi c nh y theo chi u X ả ự ằ ươ  b ng cách đ o d u các t a đ  X t ọ ố ể ị ề c là i. v  trí li n tr ề ị ọ ­ G i k là v  trí li n tr

c i, ta có X[i]­X[k]<=X[j]­X[i]. ề ướ Do đó F[i, j]= Max{F[k,i] / (cid:0) k li n tr c i}+P[j]