题解 P1679 【神奇的四次方数】

· · 题解

修订版

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

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

但是纯爆搜显然是不行的，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。

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