题目链接:https://www.lanqiao.cn/problems/2110/learning/
动态规划一直是我的弱项,这个题其实是一个很简单的动态规划的题非板子题。
这个题的精髓在于递推上面。
下面来仔细分析一下。
首先 当n =1,2,3 时 s = 1,2,5 这是可以得到的。
当每次增加一列时,我们总能得到两倍的 ai-1 这是易知的。 那么问题就在于什么时候去得到更多的L型组合呢
首先L型组合是在某一 组合下 每次增加三列可以得到。 因为L型的组合不能单独出现。而是成双出现。
这样 在确定前三项之后, 我们总能通过 a[i] = a[i-1]*2 + a[i-3] 来得到。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } const int nn = 1e7+10; const int mod = 1000000007; int a[nn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; a[1]=1,a[2]=2,a[3]=5; for(int i=4;i<=n;i++) { a[i] = a[i-1]*2%mod+a[i-3]%mod,a[i]%=mod; } cout<<a[n]<<endl; }