[NC22669] 舔狗舔到最后一无所有

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

作为队伍的核心，forever97很受另外两个队友的尊敬。
Trote_w每天都要请forever97吃外卖，但很不幸的是宇宙中心forever97所在的学校周围只有3家forever97爱吃的外卖。
如果Trote_w给forever97买了别家的外卖，forever97就会大喊“我不吃我不吃”。
但是forever97又不喜欢连续三天吃一种外卖。
如果Trote_w哪天忘了这件事并且三天给他买了同一家外卖，那么forever97就会把Trote_w的头摁进手机屏幕里。
作为Trote_w的好朋友，你能告诉他连续请forever97吃n天饭，有多少不同的购买方法吗？

输入描述:

1
2
3
多组样例
第一行一个整数T(1<=T<=20)代表测试样例数
接下来t行每行一个整数n，代表Trote_w要请forever97吃n天饭(1<=n<=100000)

输出描述:

1
输出T个整数代表方案数，由于答案太大，你只需要输出mod 1e9+7 后的答案即可。

输入

1
2
3
2
3
500

输出

1
2
24
544984352

题解:

状态转移方程：

f[0][i]表示第0家前i天购买总方案数
f[1][i]表示第1家前i天购买总方案数
f[2][i]表示第2家前i天购买总方案数

  • f[0][i]=f[1][i-1]+f[2][i-1]+f[0][i-1]

    其意思为:第i天购买第0家的方案数=第i-1天购买第1家的方案数+第i-1天购买第0家的方案数(不能三个一样的,见下文)

  • f[0][i-1]=f[1][i-2]+f[2][i-2]+f[0][i-2]

    这里把上面的f[0][i-1]拆开如下,但是如果f[0][i],f[0][i-1]都是买第0家的东西的话,那么如果再从f[0][i-2]购买第0家的东西的话,就会有三个一样的了,这样就不符合条件,那么就应该去掉f[0][i-2],然后化简式子为

  • f[0][i]=f[1][i-1]+f[2][i-1]+(f[1][i-2]+f[2][i-2])

    同理可得其他两个的状态转移方程,在这里写出初态

  • f[0][1] = 1

    1
    0;

  • f[0][2] = 3

    1
    0,0;1,0;2,0;

我们发现f[0][i]=f[1][i]=f[2][i],那么可以得到到0,到1,到2的方案数和地推公式都是一样的,于是我们可以用一个一维数组在第i次的方案数的3倍来表示:

  • dp[i]=f[0][i]+f[1][i]+f[2][i]=3f[0][i]=3f[1][i]=3f[2][i]

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

const int MOD = 1e9+7;

int dp[100010];

int main(){
    int t;
    cin >> t;
    dp[1] = 3;
    dp[2] = 9;
    for(int i=3;i<=100001;i++){
        dp[i] = (2*dp[i-2] % MOD + 2*dp[i-1] % MOD ) % MOD;
    }
    while(t--){
        int n;
        cin >> n;
        cout << dp[n] << endl;
    }
    return 0;
}

吐槽

终于开dp了,半个月之后就ACM省赛了,有点忐忑= =