良好的遊戲序列

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會盡快添加