原题链接点这里

解题思路

1.定义状态：

设 dp[i][j] 表示在第 i 天选择第 j 种花后的所有有效方案的数量，其中 j 可以取 1, 2, 3 分别代表三种花。

2.状态转移：

不能连续三天送同一种花，因此 dp[i][j] 的值可以从前两天的不同花朵转移过来。具体地：

• 如果第 i 天选择第 1 种花，第 i-1 天可以选择第 2 或第 3 种花；或者第 i 天选择第 1 种花，但第 i-2 天只能选择第 2 种或第 3 种花。

• 如果第 i 天选择第 2 种或第 3 种花同理。

状态转移方程：
f[i][1] = f[i - 1][2] + f[i - 1][3] + f[i - 2][2] + f[i - 2][3]
f[i][2] = f[i - 1][1] + f[i - 1][3] + f[i - 2][2] + f[i - 2][3]
f[i][3] = f[i - 1][1] + f[i - 1][2] + f[i - 2][1] + f[i - 2][2]

3.初始条件：

• 在第 1 天选择第 1、2、3 种花的方案数均为 1；

• 在第 2 天选择第 1、2、3 种花的方案数均为 3（不到3天可以任意选）；

即
f[1][1] = f[1][2] = f[1][3] = 1
f[2][1] = f[2][2] = f[2][3] = 3

4.最终答案：

最终方案数为第 n 天选择任何一种花的方案总数，即 dp[n][1] + dp[n][2] + dp[n][3]

代码实现

#include<bits/stdc++.h> 

using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int n, m;
ll f[N][4]; // f[i][j] 表示在第 i 天选择第 j 种花后的所有有效方案的数量，其中 j 可以取 1, 2, 3 分别代表三种花。

void solve()
{
    cin >> n;

    // 初始化
    f[1][1] = f[1][2] = f[1][3] = 1;
    f[2][1] = f[2][2] = f[2][3] = 3;

    // 状态转移方程
    for (int i = 3; i <= n; i++) {
        f[i][1] = (f[i - 1][2] + f[i - 1][3] + f[i - 2][2] + f[i - 2][3]) % mod;
        f[i][2] = (f[i - 1][1] + f[i - 1][3] + f[i - 2][2] + f[i - 2][3]) % mod;
        f[i][3] = (f[i - 1][1] + f[i - 1][2] + f[i - 2][1] + f[i - 2][2]) % mod;
    }

    // 求出结果
    ll res = ((f[n][1] + f[n][2]) % mod + f[n][3]) % mod;

    cout << res << endl;
}


int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

// Created by xiongdx on 9/29/2024