บันทึกการเข้าชั้นเรียนของนักเรียน II ใน C++

สมมติว่าเรามีจำนวนเต็มบวก n เราต้องหาจำนวนบันทึกการเข้างานที่เป็นไปได้ทั้งหมดที่มีความยาว n ซึ่งจะถือว่าคุ้มค่า เนื่องจากคำตอบอาจมีขนาดใหญ่มาก เราจะส่งคืนโดยใช้ mod 109 + 7

ในบันทึกการเข้าชั้นเรียนของนักเรียน สตริงสามารถประกอบด้วยอักขระสามตัวต่อไปนี้เท่านั้น -

'A' หมายถึงไม่อยู่
'L' แปลว่าสาย
'P' หมายถึงปัจจุบัน

การเข้าร่วมหนึ่งครั้งจะถือว่าคุ้มค่าหากไม่มี 'A' (ขาด) มากกว่าหนึ่งตัว หรือมากกว่า 'L' แบบต่อเนื่องกันมากกว่าสองตัว (สาย) เราจึงต้องหาจุดสูงสุด

หากอินพุตเป็นเหมือน 2 ผลลัพธ์จะเป็น 8 เนื่องจากเราสามารถสร้าง 8 วิธีที่เป็นไปได้ที่สามารถให้รางวัลได้ ซึ่งก็คือ [PP, AP, PA, LP, PL, AL, LA, LL] มีเพียง AA เท่านั้นที่ไม่ อยู่ที่นั่น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดฟังก์ชัน add() ซึ่งจะใช้ a, b,
- ผลตอบแทน ((a mod m) + (b mod m)) mod m
จากวิธีหลัก ให้ทำดังนี้
กำหนดอาร์เรย์ p ที่มีขนาด n + 1, อาร์เรย์ a ที่มีขนาด n + 1, อาร์เรย์ l ที่มีขนาด n + 1, อาร์เรย์ ap ที่มีขนาด n + 1 และอาร์เรย์ al ที่มีขนาด n + 1
ถ้า n เหมือนกับ 1 แล้ว −
- คืน 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
อัล[0] :=1, อัล[1] :=1, อัล[2] :=2
สำหรับการเริ่มต้น i :=3 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
- 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])
ส่งคืน add(add(p[n], l[n]), a[n])

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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));
}