Giải bài ntucoder SABO - Sắp bò

Link bài:

Thuật toán:

• Đầu tiên, khi trong hàng có 0 con bò (n = 0), ta có 1 cách xếp.
  
• Thống kê số cách xếp i con bò thành hàng (i < n), với trường hợp i ≤ k tức trong hàng chỉ có thể có nhiều nhất 1 con bò đực, số cách sắp chỉ có thể có i con bò trắng và i trường hợp trong đó có 1 con bò đực trong hàng.
  
• Trường hợp lớn hơn (Đa phần) thì số cách sắp i con bò thành hàng sẽ bao gồm 2 trường hợp:
  
  • Trường hợp 1, con bò thứ i là bò cái: Số cách xếp i con bò sẽ bằng số cách xếp i-1 con bò (Vì thêm 1 con bò cái vào cuối hàng không ảnh hưởng gì đến số cách sắp xếp nếu con bò đó không có trong hàng.
    
  • Trường hợp 2, con bò thứ i là bò đức: Số cách xếp i con bò sẽ bằng số cách xếp i-1-k con bò vì chắc chắn nếu con bò thứ i là bò đen thì trong bán kính i-k đến i sẽ không có bò đực nào nữa. ⇒ Đồng nghĩa với việc khoảng đó không thay đổi ⇒ Dẫn đến việc ta chỉ cần đếm số cách xếp của i-1-k con bò còn lại.
    
    • Công thức cho trường hợp này a= (a[i-1] +a[i-1-k] )

Code:

Mã:

#include <bits/stdc++.h>
using namespace std;

long long int a[1007], n, k;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("sabo.inp", "r", stdin);
    //freopen("sabo.out", "w", stdout);
    cin >> n >> k;
    a[0] = 1;
        for (int i = 1; i <= n; i++)
            if (i <= k){
                if (k > 1)
                a = a[i-1] + 1; else
                a = 2;
            } else a = (a[i-1] + a[i-1-k])%1000000;
        cout << a[n]%1000000;
    
    return 0;
}