练67.3  背单词

解题思路

用长度1的普通日与长度2的技能块铺满n天，但技能块之间至少一个普通日。按最后一天分类：普通结尾贡献f[n-1]；技能结尾若前面还有天则必须接一个普通日，贡献f[n-3]。基例f0=1,f1=1,f2=2。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

禁止技能越过首尾，不能在第0天或第n+1天扩展；两个技能不能紧贴。

复杂度

时间O(n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<unsigned long long> f(max(n + 1, 3));
    f[0] = 1;
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; i++)
        f[i] = f[i - 1] + f[i - 3];
    cout << f[n] << "\n";
    return 0;
}