来自"NOCOW"

#include<stdio.h>
#include<math.h>
 
int f[60001];
 
int main()
{
    int n,i,j;
    scanf("%d",&n);
    for(i=2;i<=n;i++)
        f[i]=10000000;
    f[1]=1;
    for(i=2;i<=n;i++)
    {
        double tmp=floor(sqrt(i));
        for(j=0;j<=(int)tmp;j++)
            if(f[i]>(f[i-j*j])+1)
                f[i]=f[i-j*j]+1;
    }
    printf("%d",f[n]);
    return 0;
    printf("Hey Man!");
}

VAR
  a:array [1..244] of longint;
  f:array [0..60000] of longint;
  i,j,n,min:longint;
BEGIN
  readln(n);
    for i:=1 to trunc(sqrt(n)) do a[i]:=sqr(i);
    for i:=1 to n do
      BEGIN
        min:=Maxlongint;
          for j:=1 to trunc(sqrt(i)) do
            if f[i-a[j]]<min then min:=f[i-a[j]]+1;
        f[i]:=min;
      END;
  writeln(f[n]);
END.
//from lzoi_ys

---

动归，f[i]表示，i最少由几个平方数组成，f[i]=min(f[i-sqr(j)])+1;

program cao;
const
  maxn=80000;
 
var
  f:array[-1..maxn] of longint;
  a,b,c,d,e,g,h,i,j,k,l,n,m,p,q:longint;
 
begin
  read(n);
  fillchar(f,sizeof(f),26);
  f[0]:=0;
  for i:=1 to n do
    for j:=1 to trunc(sqrt(i)+1e-7) do
      if f[i-j*j]+1<f[i] then f[i]:=f[i-j*j]+1;
  writeln(f[n]);
end.

http://www.withflying.com/?p=135

http://www.withflying.com