http://acm.timus.ru/problem.aspx?space=1&num=1073
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #define maxn 70000 6 using namespace std; 7 const int inf=99999999; 8 int dp[maxn]; 9 int main() 10 { 11 int n; 12 scanf("%d",&n); 13 for(int i=1; i<=n; i++) 14 { 15 dp[i]=inf; 16 } 17 dp[1]=1; 18 for(int i=2; i<=n; i++) 19 { 20 int k=(int)sqrt((double)i); 21 for(int j=0; j<=k; j++) 22 { 23 dp[i]=min(dp[i],dp[i-j*j]+1); 24 } 25 } 26 printf("%d ",dp[n]); 27 return 0; 28 }