良好的游戏序列

Question

是，可以在多分钟播放和B仅可以在几分钟甚至被播放。像1秒，随后在3秒，同样为B.发挥

现在好序列定义为：

（1）如果游戏是根据自己的规则，即打，A将在奇数分钟的上场时间B在偶数分钟播放。

（2）A和B在整个序列中不交替播放。

对于例如

AXAXA：X表示没有游戏上分钟，良好的顺序播放。

ABXXXB：良好序列因为两者都是根据作为第一A被播放然后B，然后再次B.

XXXX排除以及播放：良好序列。

ABXXAB：不好的序列。

考虑到玩游戏的总分钟数，计算好序列的总数。由于数字可能相当大提供答案模1000000007.

我这样做是通过创建每个字符串并检查其正确性。它是O（2^n）。我已经得到了更少的答案，例如2,3,5,9,18,38,82,177,379,803，...，n从1开始。

我该如何通过DP做到这一点？

Answer 1

此代码适合您，我添加了演示here。请检查出来

#include <iostream> 
#include <cstdio> 
using namespace std; 
#define MOD 1000000007 
int dp[100005][3][4]= {0}; 
int main() { 
    int n; 
    cin >> n; 
    dp[1][0][1] = 1; 
    dp[1][2][0] = 1; 
    for(int i=2; i<=n; i++){ 
     if(i&1){ 
      dp[i][2][0] = dp[i-1][2][0]; 
      dp[i][0][1] = dp[i-1][2][0]; 
      dp[i][2][1] = (dp[i-1][0][1] + dp[i-1][2][1]); 
      dp[i][1][3] = dp[i-1][1][3]; 
      dp[i][2][2] = (dp[i-1][1][2] + dp[i-1][2][2])%MOD; 
      dp[i][0][3] = ((dp[i-1][1][2] + dp[i-1][2][2])%MOD + (dp[i-1][1][3] + dp[i-1][0][3])%MOD)%MOD; 
     } 
     else { 
      dp[i][2][0] = dp[i-1][2][0]; 
      dp[i][1][2] = dp[i-1][2][0]; 
      dp[i][2][1] = (dp[i-1][0][1] + dp[i-1][2][1]); 
      dp[i][1][3] = ((dp[i-1][0][1] + dp[i-1][2][1])%MOD + (dp[i-1][1][3] + dp[i-1][0][3])%MOD)%MOD; 
      dp[i][2][2] = (dp[i-1][1][2] + dp[i-1][2][2])%MOD; 
      dp[i][0][3] = dp[i-1][0][3]; 
     } 
     // for(int j=0;j<=2;j++){ 
     // for(int k=0;k<=3;k++){ 
     // if(dp[i][j][k]) 
     //  printf("i=%d j=%d k=%d dp=%d\n",i,j,k,dp[i][j][k]); 
     // } 
     // } 
    } 
    int p = 1; 
    for(int i=1; i<=n; i++){ 
     p = (p*2) % MOD; 
    } 
    p = (p - dp[n][0][3] - dp[n][1][3])%MOD; 
    p = (p+MOD)%MOD; 
    cout << p << endl; 
    return 0; 
} 

Answer 2

让我们说我们有状态

1. X，XX， - 添加在b它会导致状态2，当它导致3，X状态
没有发生变化时
2. xb，xbxbx， - 当x没有状态改变时，b没有状态改变，当它导致状态5
3. a，axa， - 当x没有改变状态，当没有改变状态， b导致状态4
4. ab，xxab，abx - x no chang ES在状态，对于b它变为状态2，应该忽视添加
5. XBA，xbax - X国没有变化，对于它的变化3，对于b我们应该忽视添加B

所以您可以从小范围（长度1）到给定范围，并在添加x或a，b时对状态进行计数。

让参见长度

1. 添加和x到空字符串

   • 状态1 - 0 + 1（x）的
   • 状态2 - 0
   • 状态3 - 0 + 1 （a）
   • State4 - 0
   • State5 - 0
     

   共计2

2. 添加B和X

   • 状态1 - 1
   • 状态2 - 0 + 1（从STATE1通过添加B）
   • 状态3 - 1
   • State4 - 0 + 1（从状态3通过添加b）
   • 小号tate5 - 0
     

   共计4

3. 加入a和x

   • 状态1 - 1
   • 状态2 - 1
   • 状态3 - 1 + 1（从STATE1通过添加一个到它）+ 1（从state3本身axa ..）
   • State4 - 1
   • State5 - 0（来自STAT2通过添加到它）
     

   共计7

4. 添加B和X

   • 状态1 + 1 - 1
   • 状态2 - 1 + 1（状态1）+ 1（状态2本身）+ 1（状态4）
   • 状态3 - 3
   • State4 - 1 + 3（从状态3）
   • State5 - 1
     

   Total 13

5. 添加并且x

   • 状态1 - 1
   • State2 - 4
   • 状态3 - 3 + 1（来自STATE1）+ 3（从状态3本身）+ 1（从state5）
   • State4 - 4
   • State5 - 1 + 4（从状态2）
     

   Total 22

复杂性将是O（N）

码Wi会尽快添加