Bạn được Nguyệt Cát mời tham gia diễn đàn viết bài kiếm tiền VNO, bấm vào đây để đăng ký.
1 người đang xem
25 ❤︎ Bài viết: 28 Tìm chủ đề
3505 7
Link bài:

Thuật toán:


  • Nhận xét: Ở trường hợp n = 0, ta chỉ có 1 cách xếp các ô gạch.
  • Trường hợp n = 1, ta có 3 cách xếp các ô gạch trên.
  • Gọi số cách điểm xuyết của i ô gạch là ai: Với tường hợp thứ i (i > 1) ta có nhận xét sau:
    • Nếu ô gạch thứ i-1 có điểm xuyết là 1 0 thì ở ô thứ i, điểm xuyết là 0 0 hoặc 0 1.

    ⇒ Với số cách điểm xuyết e sao cho ô i-1 có điểm xuyết 1 0, ta có 2*e cách điểm xuyết ô thứ i.
    • Tương tự ô gạch i-1 có điểm xuyết 0 1 thì ô thứ i, điểm xuyết là 0 0 hoặc 1 0.

    ⇒ Với số cách điểm xuyết e2 sao cho ô i-1 có điểm xuyết 0 1, ta có 2*e2 cách điểm xuyết ô thứ i.
    • Nếu ô gạch thứ i-1 có điểm xuyết là 0 0 thì ô thứ i, điểm xuyết là 0 1, 1 0 hoặc 0 0.

    ⇒ Với số cách điểm xuyết e3 sao cho ô i-1 có điểm xuyết 0 0, ta có 3*e3 cách điểm xuyết ô thứ i.

    Ở điểm xuyết ô i-1 là 0 0, có thể chia thành trường hợp sau:
    • Trường hợp ô i điểm xuyết 0 1 và 1 0. Có 2*e3 trường hợp
    • Trường hợp ô i điểm xuyết 0 0 (tức sẽ bằng toàn bộ số cách điểm xuyết của ô i-2) (Ô i-1 và ô i đều có điểm xuyết 0 0).

    Tức công thức của ta là: Ai = a (i-1) *2+a (i-2)

Code:

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

int n;
int a[1007];

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

Những người đang xem chủ đề này

Xu hướng nội dung

Back