C++での学生出席記録II

正の整数nがあるとすると、長さnのすべての可能な出席レコードの数を見つける必要があります。これは報われると見なされます。答えは非常に大きい可能性があるため、mod 109+7を使用して返します。

学生の出席記録では、文字列には次の3文字のみを含めることができます-

• 「A」は不在を意味します。
• 「L」は遅いことを意味します。
• 「P」は存在を意味します。

1回の出席は、複数の「A」（不在）または2つ以上の連続した「L」（後期）が含まれていない場合、報酬として扱われます。したがって、最大ポイントを見つける必要があります。

入力が2の場合、出力は8になります。これは、報酬を得ることができる8つの可能な方法を生成できるためです。これらは、[PP、AP、PA、LP、PL、AL、LA、LL]であり、AAのみはそうではありません。そこにいる。

これを解決するには、次の手順に従います-

• 関数add（）を定義します。これには、a、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
• al [0]：=1、al [1]：=1、al [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]）
  • 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]）

理解を深めるために、次の実装を見てみましょう-

例

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

入力

3

出力

19