题目描述
题目定死了行数为2,用线性dp+前缀和,核心代码2行就足以完成了。
C++ 代码
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
const int x = 1e7+5;
long long dp[x];
long long qzh[x];
int main(){
int N;
cin>>N;
dp[0]=1;
qzh[0]=1;
for(int i=1;i<=N;++i){
dp[i]+=(qzh[i-1]*2-dp[i-1]-dp[i-2])%mod;//更新dp
qzh[i]=qzh[i-1]+dp[i];//更新前缀和
}
cout<<dp[N];
return 0;
}
时间复杂度
O(n)
分析
定义dp[i]:有i行时,不同的排布方式种数
下面定义状态转移方程:
分析dp[i]由哪些部分构成,也就是寻找dp[i]和之前的dp[i-1],dp[i-2]…之间的关系
为了保证得到的图形不重复,这样考虑:
我们去寻找第i列可能参与组成的大矩形。这样就可以利用之前的dp了。也就是,包含第i列,往左找矩形,往矩形内部填充积木,而矩形的剩余部分的排布方式总数已存在dp中,那么有:
dp[i]=(x=1~i)Σ长为x的矩形内部的排布种数n*dp[i-x]
例如:
我们往这个大矩形里填充积木。但必须注意,填充时大矩形必须无法再分成其他矩形,如图是错误填充方式:
因为这样填充,其实应该归于右边3×2的大矩形,而不是4×2的大矩形,左边那一条是可以被拿走的。重复计算了。
为什么要这样找呢?经过观察我们可以发现,一个大矩形,用这两种积木,如果要不能裂出小矩形,拼法种数是可以推演的,这一步是关键,也是比其他解法简单的地方。
如图,要使大矩形内部没有小矩形,除了宽=1,2放不下L型积木,只有1种放法,其他时候必须恰好有2个L型积木在两侧,中间横向长条环环相扣。也就是说,当宽>=3时,无论大矩形多长,都只有2种上下翻转的摆法。根据我们之前的公式:
dp[i]=(x=1~i)Σ长为x的矩形内部的排布种数n*dp[i-x]
这个”种数n”在x=1,2时为1,其他时候为2。
于是,状态转移方程中的未知量被定下来了,定义完毕,接下来要做的就是对Σ进行简化。
因为dp已经可以写作:
dp[i]=2×dp[0]+2×dp[1]+2×dp[2]+…+2×dp[i-3]+1×dp[i-2]+1×dp[i-1]
这就是代码中的:dp[i]+=(qzh[i-1]*2-dp[i-1]-dp[i-2])%mod;//更新dp
注意到这个数字就是dp的和翻倍再减去最后两项,前面的dp已经确定,不需要每次重新计算了,于是引入、维护前缀和qzh数组。
qzh[i]=qzh[i-1]+dp[i];//更新前缀和
表达能力有限,可能很多人还是不懂为什么要找大矩形。简单来说,从两个角度考虑:
1.内部不含小矩形的大矩形,随着这个矩形长度变大,图形不会重复;
2.大矩形的内部排布方式相对固定,容易处理。