[蓝桥杯2022初赛] 积木画

题目链接：2037: 蓝桥杯2022初赛 积木画

解析

是一个动态规划题目，不过一维肯定是不够的，每一个横坐标位置要有四个状态表示：

1. 上下都没有方块
2. 只有上面有方块
3. 只有下面有方块
4. 上下都有方块

记当前横坐标为 i，则 i 的四个状态都仅与 i – 1 的四个状态相关，即不允许 i – 2 以及之前的位置出现空位。

然后就是状态转移方程，只要谨慎一些还是不难得出的：

上下都没有方块

只能是从 i – 1 的上下都有方块状态，不放置任何积木决策得来。

dp[i][0] = dp[i - 1][3];

只有上面有积木

两种方式：

1. i – 1 的只有下面有积木状态，在上面放置一个横向积木决策。
2. i – 1 的只有上面有积木状态，在下面放置一个横向积木决策。

dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;

为啥不能从 i – 1 的上下都无状态，放置一个横向积木呢？因为这样会导致 i – 1 还有一个空位，当下一次迭代时没有办法填补。

只有下面有积木

两种方式，和上面的对称：

dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;

上下都有积木

这位更是重量级，有四种方式：

1. i – 1 的上下都无积木状态，放置两个横向积木决策（为啥不能放两个竖向呢？因为之前能让它无积木，就是因为拒绝了放置竖向积木这个决策。）
2. i – 1 的只有上面有积木状态，放置一个 L 积木决策。
3. i – 1 的只有下面有积木状态，放置一个 L 积木决策。
4. i – 1 的上下都有积木状态，放置一个竖向积木决策。

dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % MOD;

初始状态

将 1，2 当作特殊输入处理，遇到直接返回答案 1，2。

笔算一下 2 时的四个初始状态：

    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[2][2] = 1;
    dp[2][3] = 2;

然后从 3 开始迭代，到最后 dp[n][3] 就表示 横坐标为 n 上下都有积木方块，且每次决策都保证了不会出现空位时的摆放方法数量。

滑动窗口优化

数据规模说大不大，但每次也确实只能用到前面一层四个状态，i – 2 及之前的统统用不到，考虑定义一个 dp[2][4] 数组，然后每次对横坐标的访问对 2 取模，及 i % 2、(i + 1) % 2 等。我这里用按位与的方式替代。

int 上限问题

答案对 10 亿 + 7 取模，int 上限大约为 21 亿，而上面有一个状态转移方程用到了四个状态相加，极限情况是有可能超的，我这边直接用 long long 代替 int 解决问题。

代码

#include <iostream>

typedef long long ll;
const ll MOD = 1000000007;
int n;
ll dp[2][4]; // [0...3] 0 上下都无 1 上有 2 下有 3 上下都有
using namespace std;

int main() {
    cin >> n;
    if (n == 1) {
        cout << 1;
        return 0;
    } else if (n == 2) {
        cout << 2;
        return 0;
    }
    dp[0][0] = 1;
    dp[0][1] = 1;
    dp[0][2] = 1;
    dp[0][3] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i & 1][0] = dp[(i - 1) & 1][3];
        dp[i & 1][1] = (dp[(i - 1) & 1][0] + dp[(i - 1) & 1][2]) % MOD;
        dp[i & 1][2] = (dp[(i - 1) & 1][0] + dp[(i - 1) & 1][1]) % MOD;
        dp[i & 1][3] = (dp[(i - 1) & 1][0] + dp[(i - 1) & 1][1] + dp[(i - 1) & 1][2] + dp[(i - 1) & 1][3]) % MOD;
    }
    cout << dp[n & 1][3] << endl;
    return 0;
}