平方拆分 蓝桥杯

题目链接

因为根本不知道可以由几个数组成，所以深度优先搜索。
0不算。

#include<bits/stdc++.h>


using namespace std;

const int total=2019;
int ans=0;//记录有几个解
void dfs(int n,int val)//n为当前最大数，使组成数递增，val为当前的总和
{
	if(val>=total)//如果当前大于等于2019当然结束递归
	{
		if(val==total)
		ans++;
		return ;
	}
	for(int x=n+1;x*x+val<=total;x++)//不然的话就找下一个
	{
		dfs(x,val+x*x);
	}
}

int main()
{
	dfs(0,0);
	cout<<ans<<endl;//最终答案为26287
	return 0;
}















1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42