Bản ghi điểm chuyên cần của học sinh II trong C ++

Giả sử chúng ta có một số nguyên dương n, chúng ta phải tìm số tất cả các bản ghi tham dự có thể có độ dài n, sẽ được coi là có thưởng. Vì câu trả lời có thể rất lớn, chúng tôi sẽ trả lại nó bằng cách sử dụng mod 109 + 7.

Trong hồ sơ tham dự của học sinh, chuỗi chỉ có thể chứa ba ký tự sau -

'A' có nghĩa là vắng mặt.
'L' có nghĩa là muộn.
'P' có nghĩa là hiện tại.

một lần tham dự được coi là có thưởng nếu nó không chứa nhiều hơn một 'A' (vắng mặt) hoặc hơn hai 'L' liên tục (muộn). Vì vậy, chúng ta phải tìm điểm tối đa.

Nếu đầu vào là 2, thì đầu ra sẽ là 8, vì chúng ta có thể tạo ra 8 cách khả thi có thể được thưởng, đó là [PP, AP, PA, LP, PL, AL, LA, LL], chỉ AA thì không ở đó.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm add (), hàm này sẽ nhận a, b,
- return ((a mod m) + (b mod m)) mod m
Từ phương pháp chính, hãy thực hiện như sau,
Xác định mảng p có kích thước n + 1, mảng a có kích thước n + 1, mảng l có kích thước n + 1, mảng ap có kích thước n + 1 và mảng al có kích thước n + 1
nếu n giống 1, thì -
- trả về 3
p [0]:=1, p [1]:=1, p [2]:=3
a [0]:=1, a [1]:=1, a [2]:=2
l [0]:=1, l [1]:=1, l [2]:=3
ap [0]:=1, ap [1]:=1, ap [2]:=2
al [0]:=1, al [1]:=1, al [2]:=2
để khởi tạo i:=3, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
- p [i]:=add (add (p [i - 1], a [i - 1]), l [i - 1])
- l [i]:=add (add (p [i - 1], p [i - 2]), add (a [i - 1], a [i - 2]))
- a [i]:=add (al [i - 1], ap [i - 1])
- al [i]:=add (ap [i - 1], ap [i - 2])
- ap [i]:=add (ap [i - 1], al [i - 1])
trả về thêm (thêm (p [n], l [n]), a [n])

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
   lli add(lli a, lli b){
      return ( (a % m) + (b % m) ) % m;
   }
   int checkRecord(int n) {
      vector <int> p(n+1), a(n+1), l(n+1), ap(n+1), al(n+1);
      if(n == 1)return 3;
      p[0] = 1;
      p[1] = 1;
      p[2] = 3;
      a[0] = 1;
      a[1] = 1;
      a[2] = 2;
      l[0] = 1;
      l[1] = 1;
      l[2] = 3;
      ap[0] = 1;
      ap[1] = 1;
      ap[2] = 2;
      al[0] = 1;
      al[1] = 1;
      al[2] = 2;
      for(int i = 3; i <= n; i++){
         p[i] = add(add(p[i-1], a[i-1]), l[i-1]);
         l[i] = add(add(p[i-1], p[i-2]),add(a[i-1] , a[i-2]));
         a[i] = add(al[i-1], ap[i-1]);
         al[i] = add(ap[i-1], ap[i-2]);
         ap[i] = add(ap[i-1], al[i-1]);
      }
      return add(add(p[n], l[n]), a[n]);
   }
};
main(){
   Solution ob;
   cout << (ob.checkRecord(3));
}

Bản ghi điểm chuyên cần của học sinh II trong C ++

Ví dụ

Đầu vào

Đầu ra