称号：四方形定理。输出可以表示为一个数目不超过四个平方和表示的数。

分析：dp，完全背包。背包分割整数。可用一维分数计算，它也可以被写为一个二维团结。

             状态：设f（i，j，k）为前i个数字，取j个数字他们的平方和是k的便是方法数。

             转移：f（i，j，k）= sum（f（i-1，j-1。k-i*i））。{ 当中i能够省掉不写 }。

说明：打表计算。求和输出就可以。（2011-09-19 11:01）

#include 
     
      #include 
      
       int F[ 5 ][ 32770 ];int main(){    int i,j,k;    memset( F, 0, sizeof( F ) );    F[ 0 ][ 0 ] = 1;    for ( i =  1  ; i <=  181  ; ++ i )    for ( j =  1  ; j <=   4   ; ++ j )    for ( k = i*i ; k <= 32768 ; ++ k )        F[ j ][ k ] += F[ j-1 ][ k-i*i ];    int n;    while ( scanf("%d",&n) && n ) {        int sum = 0;        for ( i = 1 ; i <= 4 ; ++ i )            sum += F[ i ][ n ];        printf("%d\n",sum);    }    return 0;}
      
     

版权声明：本文博主原创文章，博客，未经同意不得转载。