Olimpiade Sains Provinsi (OSP) 2014 - Komputer, Nomor 8–9
Deskripsi Untuk Soal Nomor 8 dan 9
Budi ingin bermain Loncat Berhadiah. Permainan dimainkan pada sebuah kotak berukuran R x C petak. Petak kiri atas dinomori (1, 1) dan petak kanan bawah dinomori (R, C). Pada setiap petak terdapat sebuah bilangan. Budi memulai permainan dengan memilih salah satu petak pada kolom 1. Dari suatu petak (r, c), Budi harus berpindah ke petak (r, c+1), (r+1, c+1), atau (r-1, c+1). Apabila Budi sudah berada pada kolom C, permainan berakhir. Budi mendapat poin berupa jumlah seluruh bilangan yang terdapat pada petak-petak yang dilalui Budi.
8.
Berapa poin maksimum yang dapat diperoleh Budi pada kotak permainan di bawah ini?
| 2 | 5 | 5 | 1 |
| 3 | 1 | 4 | 2 |
| 4 | 2 | 3 | 3 |
9.
Berapa poin maksimum yang dapat diperoleh Budi pada kotak permainan di bawah ini?
| 1 | 7 | 9 | 10 | 3 | 5 |
| 4 | 2 | 4 | 8 | 4 | 3 |
| 5 | 3 | 5 | 5 | 6 | 1 |
| 2 | 4 | 6 | 9 | 3 | 2 |
| 3 | 5 | 6 | 1 | 2 | 5 |
5 jawaban
Anthony Anthony11 tahun lalu
6
Dengan dynamic programming:
dp[r][c] = max(dp[r][c - 1], dp[r - 1][c - 1], dp[r 1][c - 1]) value[r][c]
dengan:
- value[r][c] = nilai di baris r kolom c
- jika (r, c) berada di luar kotak maka dp[r][c] = 0
Jawab: 15
Azhar Abdurrasyid11 tahun lalu
1
4-7-9-10-4-5 jawab : 39
Hezekiel Elshaddy11 tahun lalu
1
3 + 5 +5 +2 =15
Fajar Adi10 tahun lalu
1
Dengan menggunakan algoritma djikstra, maka di dapat :
No. 8 = 15 (3+5+5+2) atau (3+5+4+3)
No.9 = 39 (4+7+9+10+4+5)
Masuk untuk menulis jawaban
