题目描述

blablabla

样例

丑陋的dp，但思路很简单
dp[N][2][2][4];
第几位，1在之前有没有用过，3在之前有没有用过，末尾是几（0,1,2,3），可以末尾是3，但前面没用过3
由于第一位只能是2
只用dp两次
一次是不管有没有0
第二次是没有0的情况
用第一次减去第二次得到答案

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

O(n)

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
const int N = 1010;
long long dp[N][2][2][4];
typedef long long ll;
int n;

int main()
{
    cin >> n;
    //第几位  1有没有出现过 3有没有出现过 末尾是0、 1、 2、 3
    //0在1 前, 
    dp[1][0][0][2] = 1;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= 3; j++)    
            dp[i][0][0][j] = dp[i-1][0][0][0] + dp[i-1][0][0][2], dp[i][0][0][j] %= p;
        for (int j = 1; j <= 3; j++)
            dp[i][1][0][j] = dp[i-1][1][0][1] + dp[i-1][1][0][2] + dp[i-1][0][0][1], dp[i][1][0][j] %= p;
        for (int j = 0; j <= 3; j++)
            if(j == 2) continue;
            else dp[i][0][1][j] = dp[i-1][0][1][3] + dp[i-1][0][1][0] + dp[i-1][0][0][3], dp[i][0][1][j] %= p;
        for (int j = 0; j <= 3; j++)
            if(j == 0 || j == 2) continue;
            else dp[i][1][1][j] = dp[i-1][1][1][1] + dp[i-1][1][1][3] + dp[i-1][1][0][3] + dp[i-1][0][1][1], dp[i][1][1][j] %= p;
    }
    ll ans = dp[n][1][1][3] + dp[n][1][1][1] + dp[n][1][0][3] + dp[n][0][1][1];
    ans %= p;
    memset(dp, 0, sizeof dp);
    dp[1][0][0][2] = 1;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= 3; j++)    
            dp[i][0][0][j] = dp[i-1][0][0][0] + dp[i-1][0][0][2], dp[i][0][0][j] %= p;
        for (int j = 1; j <= 3; j++)
            dp[i][1][0][j] = dp[i-1][1][0][1] + dp[i-1][1][0][2] + dp[i-1][0][0][1], dp[i][1][0][j] %= p;
        for (int j = 1; j <= 3; j++)
            if(j == 2) continue;
            else dp[i][0][1][j] = dp[i-1][0][1][3] + dp[i-1][0][1][0] + dp[i-1][0][0][3], dp[i][0][1][j] %= p;
        for (int j = 1; j <= 3; j++)
            if(j == 0 || j == 2) continue;
            else dp[i][1][1][j] = dp[i-1][1][1][1] + dp[i-1][1][1][3] + dp[i-1][1][0][3] + dp[i-1][0][1][1], dp[i][1][1][j] %= p;
    }
    ll tp = dp[n][1][1][3] + dp[n][1][1][1] + dp[n][1][0][3] + dp[n][0][1][1];
    tp %= p;
    cout << ((ans - tp) % p + p) % p << endl;

    return 0;
}