题解：P9416 [POI 2021/2022 R1] Domino

· · 题解

题目传送门

1. 题目大意：

已经很清楚了，无需赘述

2. 解法：

先考虑如果给一个 n，没有占用的格子，让我们求 m，正是斐波那契数列，那么我们的答案矩形，是不是可以由若干个这样的矩形拼接而成，在每两个矩形中间加上被占用的格子，用来划分。再根据乘法原理，可知，答案矩形的方案数 m，是由所有小矩阵的方案数相乘得来的，所以这个问题就转化成了，对于一个数，将其拆分成斐波那契数列中的若干项相乘。同时记录最小长度即可。注意特判 m=1 的情况。

3. code：

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

int m, ans = 9e18;
vector <int> fib;

void dfs(int shengyu, int len, int nxt) { // 当 m 还剩下的数为 shengyu，已经"拆出"了 len 个数了，上一个拆分数为 nxt
    if (shengyu == 1) {
        ans = min(ans, max(len - 1, 0ll));
        return ;
    }
    if (len >= ans) return ;
    for (int i = nxt; i >= 2; i --) {
        if (shengyu % fib[i] == 0) {
            dfs(shengyu / fib[i], len + i + 1, i);
        }
    }
    return ;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> m;
    if (m == 1) {
        cout << 1 << '\n';
        return 0;
    }
    fib.emplace_back(1);
    fib.emplace_back(1);
    while (fib[fib.size() - 1] <= m) fib.emplace_back(fib[fib.size() - 1] + fib[fib.size() - 2]); // 预处理出斐波那契数列
    dfs(m, 0, (int)(lower_bound(fib.begin(), fib.end(), m) - fib.begin()));
    if (ans == 9e18) cout << "NIE" << '\n'; // 无解
    else cout << ans << '\n'; // 有解
    return 0;
}

给我这只蒟蒻点一个赞吧