【蓝桥杯每日一题】积木画 DP

积木画

2024-12-4 蓝桥杯每日一题 积木画 DP练习

题目大意

给定两种积木,然后拼接两行的矩阵，判断完全拼完有多少种拼法。只会输入一个N，代表多少列。

解题思路

1. 观察每一列可以放的形态有多少种？ 3 种。
   1. 第一行比第二行多一个方格；
   2. 第一行和第二行都用方格；
   3. 第二行比第一行多一个方格。
2. 然后看这三种状态都可以由哪种转态转移过来？可以观察到当前这一列的状态只会与前两列有关（具体看图例），那么引入状态转移方程，这就需要三个方程了，每种状态一种。然后还有初始化，$dp[0][1]=1,dp[1][1]=1$，因为这两列都只能放 I型积木，这里有个坑，有人认为（当然那个人就是我hhh）第0列应该初始化为0啊；对于第二列中两个不相等的状态都要由谁来转移呀，那就是第0列干的活。

Accepted

#include <bits/stdc++.h>
using namespace std;
const int N = 10000010,mod = 1000000007;
int n,dp[N][3];int main()
{cin>>n;// 初始化第一列和第0列 因为从第二列开始就已经可以进行计算了dp[0][1] = 1;   // 第0列初始化为1，为了方便在第一列使用L型积木dp[1][1] = 1;   // 只有一种方式for(int i = 2;i <= n;i++) {dp[i][0] = (dp[i-1][2] + dp[i-2][1]) % mod;dp[i][1] = ((dp[i-1][0] + dp[i-1][2]) % mod + (dp[i-1][1] + dp[i-2][1]) % mod ) % mod;dp[i][2] = (dp[i-1][0] + dp[i-2][1]) % mod;}// 最后输出状态为 1 的结果即可cout<<dp[n][1]<<endl;return 0;
}