【题目来源】
洛谷：P1990 覆盖墙壁 - 洛谷 (luogu.com.cn)
【题目描述】
你有一个长为 \(N\) 宽为 \(2\) 的墙壁，给你两种砖头：一个长 \(2\) 宽 \(1\)，另一个是 L 型覆盖 \(3\) 个单元的砖头。如下图：
0 0
0 00
砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖 \(N\times 2\) 的墙壁的覆盖方法。例如一个 \(2\times 3\) 的墙可以有 \(5\) 种覆盖方法，如下：
012 002 011 001 011
012 112 022 011 001
注意可以使用两种砖头混合起来覆盖，如 \(2\times 4\) 的墙可以这样覆盖：
0112
0012
给定 \(N\)，要求计算 \(2\times N\) 的墙壁的覆盖方法。由于结果很大，所以只要求输出最后 \(4\) 位。例如 \(2\times 13\) 的覆盖方法为 \(13465\)，只需输出 \(3465\) 即可。如果答案少于 \(4\) 位，就直接输出就可以，不用加前导 \(0\)，如 \(N=3\) 时输出 \(5\)。
【输入】
一个整数 \(N\)，表示墙壁的长。
【输出】
输出覆盖方法的最后 \(4\) 位，如果不足 \(4\) 位就输出整个答案。
【输入样例】
13
【输出样例】
3465
【解题思路】
【算法标签】
《洛谷 P1990 覆盖墙壁》 #递推#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 输入的正整数n
int f[1000005] = {0, 1, 2}; // f数组存储主递推结果，初始化f[1]=1, f[2]=2
int k[1000005] = {0, 0, 1}; // k数组辅助递推，初始化k[1]=0, k[2]=1int main()
{cin >> n; // 读取输入n// 动态规划计算从3到n的值for (int i = 3; i <= n; i++) {// 主递推公式：f[i] = f[i-1] + f[i-2] + 2*k[i-1]f[i] = (f[i-1] + f[i-2] + k[i-1] * 2) % 10000;// 辅助递推公式：k[i] = f[i-2] + k[i-1]k[i] = (f[i-2] + k[i-1]) % 10000;}cout << f[n]; // 输出结果f[n]return 0;
}
【运行结果】
13
3465