自动搬运

查看原文

来自洛谷，原作者为

	x义x “我们要走多远？”“一百万年。”

搬运于2025-08-24 21:27:50，当前版本为作者最后更新于2018-04-09 13:16:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

修订版

完全背包固然是正解，但万一比赛时我们脑子瓦特想不出正解怎么办呢？

那就是我们的爆搜出场的时候了！（滑稽）

但是纯爆搜显然是不行的，$m<=100000$，这个数据范围很有可能得不了高分甚至爆0，所以我们就要进行一些优化。

首先是剪枝。我们可以用ans存下当前的最好答案，如果在搜索时当前选的数的数量已经大于ans了，那肯定就没必要找了，这样是白费力气。另外，$1^4+2^4$和$2^4+1^4$是一样的方案，不需要分别处理，我们存储一个last保证选出的数列变得不降，同样可以减少时间消耗。

另外搜的顺序非常重要。如果我们从1往上搜，那第一个选出来的肯定是全1的序列。这种情况我们肯定不想要，希望直接将其剪枝。那么怎么操作呢？结合刚才说的，我们可以确定一个娇小较小的ans，然后之后的搜索肯定不会超过这个步数。没错，从最大往小的搜可以很好地完成这个任务。如果不这样的话只会有30分。

如何实现？请看代码。

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

int n;
int ans=999999;

void dfs(int tot,int k,int last)
/*
三个参数：
tot是之前所有选的数的和，
k是选了几个数（用于更新ans）
last是上次选的数（保证不降序排列，不会出现1^4+2^4和
2^4+1^4分别处理的尴尬情况）
*/
{
	if(k>ans) return; //剪枝
	if(tot>n) return; //边界条件
	
	if(tot==n) //达到n了，更新答案
	{
		if(ans>k) ans=k;
		return;
	}
	
	int i;
	
	for(i=last;i*i*i*i<=n-tot;) i++;
	
	for(;i>=last;i--) //从后往前搜
		dfs(tot+i*i*i*i,k+1,i);
}

int main()
{
	cin>>n;
	dfs(0,0,1); //爆搜大法牛B！！！
	cout<<ans;
}

另外，这份代码虽是爆搜，但运行也是非常快的~除了#2有236ms，#9有184ms外其他都是0ms。

最后，如果您觉得这篇题解还不错的话，请记得点个赞吧~