题目链接
https://vjudge.net/contest/398864#problem/E
解题思路
3*n的一个矩形中铺满1*2的矩形，问对于不同的n，存在多少种相应的铺法。首先明白一点，n必定为偶数；若n为奇数，那么格子的总数为3*奇数，必定为奇数，而每个填充的矩阵的大小为2，所以无法完全覆盖大矩形本题是通过递归关系求解的：假设要求列数为n的大矩阵被覆盖的方案数，用dp[n]表示；列数为n的大矩阵被覆盖的方案数 = 列数为2的大矩阵被覆盖的方案数 * 列数为n-2的大矩阵被覆盖的方案数 + 列数为4的大矩阵被覆盖的方案数 * 列数为n-4的大矩阵被覆盖的方案数 + 列数为6的大矩阵被覆盖的方案数 * 列数为n-6的大矩阵被覆盖的方案数 + ……注意：其实“列数为4的大矩阵被覆盖的方案数”中有些方案与“列数为2的大矩阵被覆盖的方案数”中的方案重复，这代表我们把同一个方案算了不止一次；“列数为6的大矩阵被覆盖的方案数”与“列数为4的大矩阵被覆盖的方案数”也存在重复多算的情况。画个图好理解：上图为“列数为2的大矩阵被覆盖的方案数 * 列数为n-2的大矩阵被覆盖的方案数”的其中一种情况；下图为“列数为4的大矩阵被覆盖的方案数 * 列数为n-4的大矩阵被覆盖的方案数”的其中一种情况，很显然，这俩是一种覆盖方案吧，这就是重复的部分。也就是说我们每次相乘再累加的乘号左侧的乘数其实表示的是不重复的覆盖方案数以上这两种情况才是“列数为4的大矩阵被覆盖的方案数 * 列数为n-4的大矩阵被覆盖的方案数”与“列数为2的大矩阵被覆盖的方案数 * 列数为n-2的大矩阵被覆盖的方案数”不同的覆盖方式，个数为2。怎么才能推出来每种方案与前面方案不重复的个数？仔细思考会明白不同之处出现在分割线的位置，如果分割线正好贯穿了两个小矩形，此时对应的就是不重复的情况，又由于可以上下翻转一次，所以，每次个分割线处会有2个不重复的情况。依次类推，除了“列数为2的大矩阵被覆盖的方案数”=3外，其他的乘号左侧的乘数都为2。递归方程： f(n) = 3 * f( n - 2 ) + 2 * ( f ( n - 4 ) + f ( n - 6 ) + ...+ f(0) )进一步优化递归方程：由 f( n - 2 ) = 3 * f( n - 4 ) + 2 * ( f ( n - 6 ) + f ( n - 8 ) + ...+ f(0) )=> f( n - 2 ) - f( n - 4 )= 2 * ( f( n - 4 ) + f ( n - 6 ) + f ( n - 8 ) + ...+ f(0) )代入递归方程得：f(n) = 4 * f( n - 2 ) - f( n - 4 )
AC代码
#include<iostream>
#include<cstdio>
#define ll long long
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%lld\n",x)
using namespace std;
const int N=35;
int n;
ll dp[N];
void Solve(){
dp[0]=1;dp[2]=3;
for(int i=4;i<=30;i+=2){
dp[i]=4*dp[i-2]-dp[i-4];
/*
//低配版
ll sum=0;
for(int j=i-2;j>=0;j-=2)
sum+=dp[j];
dp[i]=2*sum+dp[i-2];
*/
}
}
int main(){
Solve();
while(~sc(n)&&n!=-1){
pr(dp[n]);
}
}另附类似简单的一题
解题思路
比上个题简单多了。
很显然，斐波那契嘛。
找一下转移方程
假设有n列，第i列如何由前面得到；无非两种情况，第一种：前i-1列随便放，第i列竖着放；第二种：前i-2列随便放，第i-1列和第i列横着放两个。所以转移方程就是斐波那契。
AC代码
#include<iostream>
#include<cstdio>
#define ll long long
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%lld\n",x)
using namespace std;
const int N=55;
int n;
ll dp[N];
void Solve(){
dp[0]=1;dp[1]=1;
for(int i=2;i<=50;i++){
dp[i]=dp[i-1]+dp[i-2];
}
}
int main(){
Solve();
while(~sc(n)){
pr(dp[n]);
}
}
京公网安备 11010502036488号