首页 > 代码库 > URAL 1073 Square Country（DP）

URAL 1073 Square Country（DP）

2024-07-06 09:41:14   233人阅读

题目链接

题意 ：这个人要投资地，每块地都是正方形并且边长都是整数，他希望他要买的地尽量的少碎块。每买一块地要付的钱是边长的平方，而且会得到一个一份证书，给你一个钱数，让你求出能得到的证书个数。

思路 ：其实就是求x12+x22+……+Xn2中的最小的n。

 1 //1073
 2 #include <stdio.h>
 3 #include <iostream>
 4 #include <math.h>
 5 
 6 using namespace std ;
 7 
 8 int a[60005] ;
 9 
10 void dp()
11 {
12     for(int i = 2 ; i <= 60005 ; i++)
13         a[i] = 999999999 ;
14     a[1] = 1;
15     for(int i = 2 ; i <= 60005 ;i++)
16     {
17         for(int j = 1 ; j <= (int)sqrt(i) ; j++)
18             a[i] = min(a[i],a[i-j*j]+1 );
19     }
20 }
21 int main()
22 {
23     int n ;
24     dp() ;
25     scanf("%d",&n) ;
26     printf("%d\n",a[n]) ;
27     return 0 ;
28 }
View Code

 


联系
我们