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

1. 题目大意：

已经很清楚了，无需赘述

2. 解法：

先考虑如果给一个

n

，没有占用的格子，让我们求

m

，正是斐波那契数列，那么我们的答案矩形，是不是可以由若干个这样的矩形拼接而成，在每两个矩形中间加上被占用的格子，用来划分。再根据乘法原理，可知，答案矩形的方案数

m

，是由所有小矩阵的方案数相乘得来的，所以这个问题就转化成了，对于一个数，将其拆分成斐波那契数列中的若干项相乘。同时记录最小长度即可。注意特判

m=1

的情况。

3. code：

CPP

#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;
}

~~给我这只蒟蒻点一个赞吧~~

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

文章操作

1. 题目大意：

2. 解法：

3. code：

相关推荐

评论

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