Giải bài ntucoder LAGA - Lát gạch

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 = (a[i-1]*2 + a[i-2])%100000000;
        cout << a[n];
    }
  
    return 0;
}