西安企业网站设计机构,国外浏览器app,北京做商铺的网站,网站建设新手教程视频教程题意#xff1a;给出一个数n(1n60000),这个数可以写成一些数的平方的和#xff0c; 问对于n#xff0c;最少可以分成多少个数的平方的和。 比如#xff1a;n344#xff0c;则34418*184*42*2#xff0c;输出3. dp[i]表示i这个数最少可以分成多少个数的平方的和。 … 题意给出一个数n(1n60000),这个数可以写成一些数的平方的和 问对于n最少可以分成多少个数的平方的和。 比如n344则34418*184*42*2输出3. dp[i]表示i这个数最少可以分成多少个数的平方的和。 则遍历一边。 1 #includecstdio2 #includecstring3 #includecmath4 #includealgorithm5 6 using namespace std;7 8 const int maxn600003;9 const int inf0x3f3f3f3f;
10
11 int dp[maxn];
12
13 int main()
14 {
15 dp[0]0;
16 dp[1]1;
17 dp[2]2;
18 dp[3]3;
19 dp[4]1;
20 for(int i5;imaxn;i)
21 {
22 dp[i]inf;
23
24 for(int j1;j*ji;j)
25 {
26 dp[i]min(dp[i],dp[i-j*j]1);
27 }
28 }
29
30 int n;
31
32 while(scanf(%d,n)!EOF)
33 {
34 printf(%d\n,dp[n]);
35 }
36
37 return 0;
38 } View Code 转载于:https://www.cnblogs.com/-maybe/p/4482058.html
