1 solutions

  • 0
    @ 2021-11-16 14:35:07

    这道题,首先看N的值能够取到1000,说明递归已经无法解决问题了,只能从递推入手,N==1N==1时 有一种方案,N==2N==2时,有3种方案;当N==3N==3时,左边取两列,右边只有一种方案,左边将222*2 的放上面或者下面有两种,为什么不在左边全部放1*1,因为会在之后发生重复;左边取一列,右边就是 N==2时候的情况;所以我们就能得到递推公式F(i)=F(i1)+2F(i2)F(i)=F(i-1)+2*F(i-2). 代码如下:

    #include <bits/stdc++.h>
    using namespace std;
    int f[1005];
    int main()
    {
    	f[1]=1,f[2]=3;
    	int n;
    	cin>>n;
    	for(int i=3;i<=n;++i)
    	f[i]=(f[i-1]+2*f[i-2])%12190116;//根据所推出的递推公式,计算出题目所给范围内的方案数 
    	cout<<f[n]<<endl;
    }
    
    • 1

    Information

    ID
    156
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    6
    Tags
    # Submissions
    25
    Accepted
    11
    Uploaded By