题解 | #Jerry#

• 题意：一个数可以有两个整数相乘得到，即叫它平方数。加或减一次平方数为一次操作，现在题目问从0开始，通过若干次操作得到一个的d[i],问最少经过操作可以得到。
• 思路：从0开始深搜，将所有的数都深搜一遍，并找出最少操作次数。
• 问题：深搜何时停止，我不可能让深搜一直搜下去，否则一定超时。
• 解决问题：找出搜索最大次数p，即dfs的剪枝过程，现在我知道p最大为4，下面是论证。 可以很轻松的得出所有的平方数只要搜索1次，然后我们看两个平方之间的数要搜索几次。 (n+1)^2-(n)^2=2n+1,由于数的两边是对称的，那么就是看1~n要几次搜索， 而同上个式子我们又发现任意两个相邻的平凡数相减为任意一个奇数，那么可知如果d[i]为一个平方数加一个奇数，最多要3次，即小于它的最大的平方数加上两个相邻的平方数相减。而如果d[i]为一个平方数加一个偶数，那么就在上面过程的基础上加一个1，即最大搜索次数为4。最后得出最多搜索4次。

#include<iostream>
#include<cstring>
using namespace std;
int idx=0,a[100010];
int d[100010];
void dfs(int x,int p)
{
    if(x<0||x>100000||p>4||a[x]<=p) return;
    a[x]=min(a[x],p);//找到到x的最短操作数
    for(int i=1;i<=idx;i++)
    {
        dfs(x+d[i],p+1);
        dfs(x-d[i],p+1);
    }
}
int main()
{
    memset(a,0x3f,sizeof a);//初始化
    for(int i=1;i*i<=100000;i++)//找出所有平方数
    {
        d[++idx]=i*i;
    }
    dfs(0,0);
    int q;
    cin>>q;
    while(q--)
    {
        int t;
        cin>>t;
        cout<<a[t]<<endl;
    }
}