Pada sebuah permainan, seorang ksatria mula-mula berada pada posisi (1,1) dan hendak pergi ke posisi (6,6) untuk menyelamatkan seorang putri yang cantik. Setiap petak permainan dapat berisi vitamin atau racun. Petak yang berisi vitamin dilambangkan dengan bilangan positif pada peta, yaitu ramuan yang akan menambah kekuatan ksatria, atau Petak yang berisi racun dilambangkan dengan bilangan negatif pada peta, yaitu ramuan yang akan mengurangi kekuatan ksatria. Pada permainan ini, ksatria hanya bis

(Updated : terimakasih Reynaldo Wijaya dan Mamat Rahmat sudah menyadarkan kalau sebelumnya salah) Jika kita menginginkan kekuatan pada petak[r][c] semaksimum mungkin maka kita bisa menghitungnya dengan : petak[r][c] = max(petak[r][c] + petak[r-1][c], petak[r][c] + petak[r][c-1]) Kita dapat menghitungnya mulai dari baris paling atas. Untuk baris pertama tentunya yang maksimum adalah dari sebelah kirinya dan untuk kolom pertama tentunya yang maksimum adalah dari atasnya. Kita juga coba tracking ap

← Kembali ke Olimpiade Sains Provinsi (OSP) 2016 - Komputer

Olimpiade Sains Provinsi (OSP) 2016 - Komputer, Nomor 6

Sebelumnya Tulis Jawaban Selanjutnya

Pada sebuah permainan, seorang ksatria mula-mula berada pada posisi (1,1) dan hendak pergi ke posisi (6,6) untuk menyelamatkan seorang putri yang cantik. Setiap petak permainan dapat berisi vitamin atau racun.

Petak yang berisi vitamin dilambangkan dengan bilangan positif pada peta, yaitu ramuan yang akan menambah kekuatan ksatria, atau
Petak yang berisi racun dilambangkan dengan bilangan negatif pada peta, yaitu ramuan yang akan mengurangi kekuatan ksatria.

Pada permainan ini, ksatria hanya bisa berjalan ke arah timur atau selatan (tidak bisa melangkah secara diagonal). Ksatria tidak pernah boleh kehabisan kekuatan (kekuatan bernilai negatif atau 0) selama permainan berlangsung, termasuk pada awal permainan, dan semua ramuan pada petak-petak yang dilewati ksatria harus diminum. Tentukan jumlah kekuatan awal minimum yang harus dimiliki ksatria pada awal permainan agar ksatria tersebut dapat menyelamatkan sang putri dan memenangkan permainan!

2 jawaban

Ali Jaya Meilio10 tahun lalu

Jadi... Pada awalnya aku pakai fungsi rekursif seperti ini...

$f(y, x)$

Dimana fungsi tersebut mengembalikan jumlah kekuatan awal minimum untuk sampai ke petak (y, x) dari petak (1, 1).

Tapi ternyata ini gak bisa dicari relasi fungsinya... karena untuk mengetahui f(y, x) tidak cukup untuk mengetahui f(y-1, x) dan f(y, x-1) saja, karena kekuatan awal minimum petak sebelumnya.

Jadi... gua buat fungsi baru... namanya fungsi g (singkatan dari ganteng)

$g(y, x)$

Dengan definisi sebagai berikut... fungsi g mengembalikan kekuatan awal minimum yang diperlukan misalnya kita mulainya di petak (y, x) dan mau menuju petak (6, 6).

Dan ketemu deh relasinya... Misalkan untuk g(kiri) itu lebih kecil dari g(bawah), artinya mending kita pilih yang kiri karena pasti lebih optimal, begitu juga sebaliknya.

Long story short... (mager nulis banyak2, fungsi g jadi kayak gini)

$g(y, x) = max(1, -petak[y][x] + min(f(y+1, x), f(y, x+1)))$

Dimana base case nya itu ini

$g(6, 6) = max(1, -petak[y][x] + 1)$

Dimana kalau lewat dari batas jadi gini

$g(y, x) = \infty, \text{jika } y > 6 \text{ atau } x > 6$

Trus seperti biasa... DP Bottom Up... ini tabelnya

83	60	71	54	62	127
64	86	61	63	52	117
81	61	3	31	7	52
70	79	32	1	11	31
60	49	1	18	1	56
57	71	1	1	1	42

Jadi jawabannya ada di g(1, 1) = 83

Kode: http://ideone.com/wod9mb

Masuk untuk menulis jawaban

-23	-12 (kiri)	-29 (kiri)	-21 (kiri)	-31 (kiri)	-41 (kiri)
-6 (atas)	-31 (kiri	-87 (atas)	-53 (atas)	-76 (atas)	-106 (atas)
-26 (atas)	-84 (kiri)	-56 (kiri)	-83 (atas)	-72 (atas)	-93 (kiri)
-36 (atas)	-83 (kiri)	-87 (atas)	17 (atas)	7 (kiri)	32 (kiri)
-47 (atas)	-95 (kiri)	-58 (atas)	0 (atas)	9 (atas)	18 (atas
-33 (atas)	-103 (kiri)	22 (atas)	42 (kiri)	83 (kiri)	42 (kiri)

-23	-12 (kiri)	-29 (kiri)	-21 (kiri)	-31 (kiri)	-41 (kiri)
-6 (atas)	-31 (kiri	-87 (atas)	-53 (atas)	-76 (atas)	-106 (atas)
-26 (atas)	-84 (kiri)	-56 (kiri)	-83 (atas)	-72 (atas)	-93 (kiri)
-36 (atas)	-83 (kiri)	-87 (atas)	17 (atas)	-82 (atas)	32 (kiri)
-47 (atas)	-95 (kiri)	-58 (atas)	0 (atas)	-80 (atas)	18 (atas
-33 (atas)	-103 (kiri)	22 (atas)	42 (kiri)	-39 (atas)	-80 (kiri)

-23	-12 (kiri)	-29 (kiri)	-21 (kiri)	-31 (kiri)	-41 (kiri)
-6 (atas)	-31 (kiri	-87 (atas)	-53 (atas)	-76 (atas)	-106 (atas)
-26 (atas)	-84 (kiri)	-56 (kiri)	-83 (atas)	-72 (atas)	-93 (kiri)
-36 (atas)	-83 (kiri)	-87 (atas)	-17 (atas)	7 (kiri)	32 (kiri)
-47 (atas)	-95 (kiri)	-58 (atas)	0 (atas)	9 (atas)	18 (atas
-33 (atas)	-103 (kiri)	22 (atas)	20 (atas)	61(kiri)	20(kiri)

-23	-12 (kiri)	-29 (kiri)	-21 (kiri)	-31 (kiri)	-41 (kiri)
-6 (atas)	-31 (kiri	-87 (atas)	-53 (atas)	-76 (atas)	-106 (atas)
-26 (atas)	-84 (kiri)	-56 (kiri)	-83 (atas)	-72 (atas)	-93 (kiri)
-36 (atas)	-83 (kiri)	-87 (atas)	-17 (atas)	7 (kiri)	32 (kiri)
-47 (atas)	-95 (kiri)	-58 (atas)	0 (atas)	9 (atas)	18 (atas
-33 (atas)	-103 (kiri)	22 (atas)	20 (atas)	61(kiri)	20(kiri)

83	60	71	54	62	127
64	86	61	63	52	117
81	61	3	31	7	52
70	79	32	1	11	31
60	49	1	18	1	56
57	71	1	1	1	42

83	60	71	54	62	127
64	86	61	63	52	117
81	61	3	31	7	52
70	79	32	1	11	31
60	49	1	18	1	56
57	71	1	1	1	42

83	60	71	54	62	127
64	86	61	63	52	117
81	61	3	31	7	52
70	79	32	1	11	31
60	49	1	18	1	56
57	71	1	1	1	42