C++의 학생 출석 기록 II

<시간/>

양의 정수 n이 있다고 가정하고 길이가 n인 가능한 모든 출석 기록의 수를 찾아야 하며 이는 보상 가능한 것으로 간주됩니다. 답변이 매우 클 수 있으므로 mod 109 + 7을 사용하여 반환합니다.

학생 출석 기록에서 문자열은 다음 세 문자만 포함할 수 있습니다. -

'A'는 부재를 의미합니다.
'L'은 늦다는 뜻입니다.
'P'는 현재를 의미합니다.

하나 이상의 'A'(결석) 또는 2개 이상의 연속 'L'(늦음)을 포함하지 않는 경우 하나의 출석은 보상 가능한 것으로 처리됩니다. 그래서 우리는 최대 점수를 찾아야 합니다.

입력이 2와 같으면 출력은 8이 됩니다. 보상받을 수 있는 8가지 가능한 방법을 생성할 수 있기 때문입니다. [PP, AP, PA, LP, PL, AL, LA, LL], AA만 거기 있어.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

add() 함수를 정의하면, b,
- return ((a mod m) + (b mod m)) mod m
메인 방법에서 다음을 수행합니다.
크기 n + 1의 배열 p, 크기 n + 1의 배열 a, 크기 n + 1의 배열 l, 크기 n + 1의 배열 ap 및 크기 n + 1의 배열 al 정의
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의 경우, i <=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])
- 알[i] :=add(ap[i - 1], ap[i - 2])
- ap[i] :=add(ap[i - 1], al[i - 1])
추가(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));
}