P8784 [蓝桥杯 2022 省 B] 积木画 题解

· · 题解

题目传送门：P8784 [蓝桥杯 2022 省 B] 积木画

思路

其实这道题就是 dp。

状态表示：f_i 表示 N=i 时的方案数。

状态转移：

我们想 I 型积木开始，这个积木可以放在头和尾，所有方案数是 2\times f_{i-1}。

再从 L 积木下手，我们可以把

1223
1123

作为一个整体，于是方案数就是 f_{i-3}，注意这里不用乘 2，因为，如果放在尾巴和尾巴放 I 型积木，是一样的。

综上所述，方程就是 f_i=2\times f_{i-1}+f_{i-3}。

由于这里 1\le N\le 10^7 不能开数组，所以只能用滚动数组了，具体看代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
main(){
    int n;
    cin>>n;
    int a=1,b=2,c=5,d;
    if (n==1){//特判
        cout <<1;
        return 0;
    }
    if (n==2){
        cout <<2;
        return 0;
    }
    if (n==3){
        cout <<5;
        return 0;
    }
    for (int i=4;i<=n;i++) //dp过程
        d=c*2%mod+a,a=b,b=c,c=d,a%=mod,b%=mod,c%=mod,d%=mod;
    cout <<d;
    return 0;
}