17:I[47391,["/_next/static/chunks/5dfef289cb04e0d9.js","/_next/static/chunks/907bebc31f87fd4a.js","/_next/static/chunks/9687139162ab4107.js","/_next/static/chunks/742e2a32a13ad5f5.js"],"default"] 18:I[34621,["/_next/static/chunks/5dfef289cb04e0d9.js","/_next/static/chunks/907bebc31f87fd4a.js","/_next/static/chunks/9687139162ab4107.js","/_next/static/chunks/742e2a32a13ad5f5.js"],"default"] 19:T521,

Untuk soal ini, saya menggunakan DP;

Misal saya definisikan :

a(n) = banyak cara menempatkan 0 pada string dengan panjang n;

b(n) = banyak cara menempatkan 1 pada string dengan panjang n;

c(n) = banyak cara menempatkan 2 pada string dengan panjang n;

Misal f(n) = banyak cara menyusun string dengan panjang n, maka :

f(n) = a(n) + b(n) + c(n) ;

Karena selisih maksimal hanya 1, maka:

a(n) = a(n - 1) + b(n - 1);

b(n) = a(n - 1) + b(n - 1) + c(n - 1);

c(n) = b(n - 1) + c(n - 1);

Base case : a(1) = 1, b(1) = 1, c(1) = 1;

Dari f(n) = a(n) + b(n) + c(n), maka b(n) = a(n - 1) + b(n - 1) + c(n - 1) = f(n - 1);

Maka, f(n) = 2 * [a(n - 1) + b(n - 1) + c(n - 1)] + b(n - 1) = 2 * f(n - 1) + f(n - 2);

Dengan f(1) = a(1) + b(1) + c(1) = 1 + 1 + 1 = 3 dan f(2) = 7(diketahui dari soal), maka kita bisa mencari f(3) dan seterusnya;

f(3) = 2 * 7 + 3 = 17;

f(4) = 2 * 17 + 7 = 41;

f(5) = 2 * 41 + 17 = 99;

f(6) = 2 * 99 + 41 = 239;

f(7) = 2 * 239 + 99 = 577;

f(8) = 2 * 577 + 239 = 1393;

f(9) = 2 * 1393 + 577 = 3363;

f(10) = 2 * 3363 + 1393 = 8119(A);

Maaf jika ada kesalahan..

WAS 1314

Jawaban terbaru