Gợi ý bài quy hoạch động trên ntucoder

[Black_While]

Em mới học QHĐ trên ntucoder, gặp bài này thấy khó nhai quá xin các cao nhân cho em gợi ý làm bài vs :3 (đừng ghi mỗi công thức nha :v)

---

Anh nông dân Bo có một đàn bò gồm rất nhiều con cái và con đực. Trong một hội chợ, anh muốn sắp một hàng bò gồm n con. Tuy nhiên những con bò đực rất hung hăng nếu đứng gần nhau, anh phải sắp tối thiểu k con bò cái xen giữa hai con bò đực để chúng khỏi húc nhau.

Bạn hãy giúp anh Bo đếm thử xem có bao nhiêu cách để sắp một hàng gồm n con bò mà hai con bò đực bất kỳ không húc nhau (anh Bo có rất nhiều bò nên không sợ thiếu bò cái hoặc bò đực)

Ví dụ với n = 4 và k=1, ta có 8 cách xếp như sau (M: bò đực, F: bò cái):
FFFF, MFFF, FMFF, FFMF, FFFM, MFMF, MFFM, FMFM.

Dữ liệu nhập:

• Gồm hai số nguyên n và k cách nhau một khoảng trắng ( 1 ≤ n, k ≤ 1.000)

Dữ liệu xuất:

• Số cách xếp hàng thỏa mãn yêu cầu. Do số lượng này có thể rất lớn nên chỉ cần in ra tối đa 6 chữ số cuối cùng (modulo 1.000.000)

Ví dụ

input	output
4 1	8
5 2	9

[Nobita004 (Kirito-kun)]

Thực chất là bài là số dãy nhị phân chứa nhiều hơn hoặc bằng k kí tự 0 liên tiếp và không có 2 kí tự 1 nào liên tiếp nhau. (Nếu ta coi bò cái là 0, còn bò đực là 1).
Dễ dàng thấy:

• Nếu đến kí tự i, nếu chọn 0 thì số cách thoả mãn sẽ là số dãy nhị phân có độ dài i-1 thoả mãn đề bài. Vì ta thêm vào các dãy đó sẽ thoả mãn đề bài.
• Nếu đến kí tự i, nếu chọn 1 thì bắt buộc i-k đến i-1 bắt buộc phải là số 0 vì nếu số 1 sẽ không thoả mãn. Tức số cách sẽ là số dãy nhị phân có độ dài i-k-1 thoả mãn đề bài.
  Vậy nếu ta gọi F[i] là số dãy nhị phân có độ dài i thoả mãn đề ra thì F[i]=F[i-1]+F[i-k-1];
  Kết quả bài toán sẽ là F[n];

• Cơ sở quy hoạch động sẽ là F[1] đến F[k+1] là số dãy nhị phân không chứa 2 số 1 nào liên tiếp hay F[i]=i+1;

[rogp10]

F[i]=F[i-1]+F[i-k-1];

Để ý đây là công thức của bài đi thang nhảy bậc {1, k+1} (k+1 là bit 1 + k bit 0). Vấn đề nằm ở chỗ này.

sắp tối thiểu k con bò cái xen giữa hai con bò đực để chúng khỏi húc nhau.

[Black_While]

tks bạn nha