#1372 : 平方求和
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
对于一个非负整数n,最少需要几个完全平方数,使其和为n?
输入
输入包含多组数据。对于每组数据:
第一行是n;如果n为-1,表示输入结束。(0 <= n <= 1000000001)
输出
针对每组数据,输出最少需要的完全平方数。
- 样例输入
-
3
4
5
-1 - 样例输出
-
3
1
2
思路:
拿到这个题,我第一想到的是贪心,每次减去一个最大数的平方,但是有时候这样会得不到正确的答案,比如19 ,贪心的话就是4,1,1,1.。。。正确的应该是3,3,1.。。。
然后dp,dp虽然可以得到正确的答案,但是时间复杂度高了。pass。
在想到搜索
让我们可视化一下,
原来是个搜索的题目。
如何加速?
我们应该深度优先搜索吗?
当然不是啦!因为我们求的是最少的拆解,所以应该宽度优先搜索。
宽搜的时候,用一个last和一个nlast分别记录当前行的最后一个元素,和下一行的最后一个元素。
如何再加速?
如果我们为了收敛快,似乎方向反了。
如何再加速?
我们有些节点是不是可能重复访问?建立一个hash表存一下吧。
如何再快呢?
证明题:每个正整数都可以表示为4个完全平方数的和。
什么?居然还需要数论的知识。我不知道怎么办?
没什么啊,我们刚才的宽度优先搜索已经能够保证和这个算法是一个复杂度了。
代码:
宽搜:
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std; //
int bfs(long long n)
{
queue<long long> q;
int t = ;
long long head,last=n,nlast; //last当前行最右,nlast下一行最右
q.push(n);
while (!q.empty())
{
head = q.front();
if (t == )
{
int c = ;
} if (t == )
break;
q.pop();
if (head != )
{
for (int i = sqrt(head); i > ; i--)
{
if (head - i*i == )
return t;
q.push(head-i*i); nlast = head - i*i;
} if (head == last && !q.empty())
{
t++;
last = nlast;
}
}
}
} int main()
{
long long n;
while (cin>>n)
{
if (n == -)
break;
cout<< bfs(n)<<endl; }
system("pause");
return ;
}
数论方法AC:
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std; //
bool is_sqrt(long long n)
{
int m = sqrt(n);
if (m*m == n)
return true;
else
return false;
} int solve(long long n)
{
if (is_sqrt(n))
return ;
while (n % == )
n /= ; if (n % == )
return ; for (int i = ; i*i < n; i++)
{
if (is_sqrt(n - i*i))
return ;
}
return ;
} int main()
{
long long n;
while (cin>>n)
{
if (n == -)
break;
cout<< solve(n)<<endl; }
system("pause");
return ;
}