hdu 1398

題目大意：輸入是一個整數。輸出他的拆分數(即拆分的方案數),本題與1028最大的不同之處就在於他的面額只能是整數的平方

代碼如下：

/* 
 * 1398_1.cpp 
 * 
 *  Created on: 2013年8月9日 
 *      Author: Administrator 
 */  
  
  
#include <stdio.h>   
  
  
int main(){  
  
    //數組要開到比n值大   
    int n , c1[310],c2[310];  
  
    while(scanf("%d",&n),n){  
        int i,j,k;  
        for(i = 0 ; i <= n ; ++i){  
            c1[i] = 1;  
            c2[i] = 0;  
        }  
  
        for(i = 2 ; i*i <= n ; ++i){  
            for(j = 0 ; j <=n ; ++j){  
                for(k = 0 ; k+j <= n ; k+=i*i ){  
                    c2[j+k] += c1[j];  
  
                }  
            }  
  
            for(j = 0 ; j <= n ; ++j){  
                c1[j] = c2[j];  
                c2[j] = 0;  
            }  
        }  
  
        printf("%d\n",c1[n]);  
    }  
}  

/*
 * 1398_1.cpp
 *
 *  Created on: 2013年8月9日
 *      Author: Administrator
 */


#include <stdio.h>


int main(){

	//數組要開到比n值大
	int n , c1[310],c2[310];

	while(scanf("%d",&n),n){
		int i,j,k;
		for(i = 0 ; i <= n ; ++i){
			c1[i] = 1;
			c2[i] = 0;
		}

		for(i = 2 ; i*i <= n ; ++i){
			for(j = 0 ; j <=n ; ++j){
				for(k = 0 ; k+j <= n ; k+=i*i ){
					c2[j+k] += c1[j];

				}
			}

			for(j = 0 ; j <= n ; ++j){
				c1[j] = c2[j];
				c2[j] = 0;
			}
		}

		printf("%d\n",c1[n]);
	}
}