Blog·Tanky WooABOUTRSS

HDOJ 1398 Square Coins

02 Aug 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1398

这题和HDOJ 1028基本没区别,也是套模板。 要说区别,就只需要改2个地方。 在i遍历表达式时(可以参考我的资料---《母函数详解》),把i<=nNum改成了ii<=nNum,其次在k遍历指数时把k+=i变成了k+=ii; Ok,说来说去还是套模板~~~

代码:

 // Author: Tanky Woo
// HDOJ 1398
#include 
using namespace std;

int c1[310], c2[310];
int main()
{
    int nNum;
    while(scanf("%d", &nNum;) && nNum)
    {
        // 初始化
        for(int i=0; i<=nNum; ++i)
        {
            c1[i] = 1;
            c2[i] = 0;
        }
        for(int i=2; i*i<=nNum; ++i)
        {
            for(int j=0; j<=nNum; ++j)
                for(int k=0; k+j<=nNum; k+=i*i)
                    c2[k+j] += c1[j];
            for(int j=0; j<=nNum; ++j)
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        printf("%d\n", c1[nNum]);
    }
    return 0;
}