1 solutions
-
0
这道题,首先看N的值能够取到1000,说明递归已经无法解决问题了,只能从递推入手,时 有一种方案,时,有3种方案;当时,左边取两列,右边只有一种方案,左边将 的放上面或者下面有两种,为什么不在左边全部放1*1,因为会在之后发生重复;左边取一列,右边就是 N==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