P4133 [BJOI2012]最多的方案 题解

P4133

双倍经验

发现斐波那契数列增长极快，不到 \(100\) 项就超过了 \(10^{18}\)，搜索树也极为稀疏，可以考虑搜索。

爆搜肯定会超时，考虑优化：

1. 可行性剪枝。

2. 记忆化，去除重复的计算。

3. 改变搜索的顺序，因为先考虑小元素的话，会有较多的无用的搜索，且小元素较灵活，更容易凑到 \(x\)，故可以从大到小的考虑。

加上这三个优化即可通过此题。

时间复杂度：\(\mathcal{O}\)（可过）

const int N = 100, mod = 998244353;
const ll INF = 1e18;
int n, q;
ll a[N], sum[N];
map<ll, ll> dp[N];

ll dfs(ll x, int cur) {
	if (x < 0 || x > sum[cur]) return 0;
	if (!cur || !x) return (x == 0);
	if (dp[cur].count(x)) return dp[cur][x];
	return dp[cur][x] = dfs(x - a[cur], cur - 1) + dfs(x, cur - 1);
}

int main() {
	n = 1, a[0] = a[1] = 1;
	int m = n;
	while (a[m] <= INF) {
		a[++m] = 0;
		a[m] = a[m - 1] + a[m - 2];
	}
	n = m - 1;
	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
	ll x;
	cin >> x;
	cout << dfs(x, n) << endl;
	return 0;
}