HDOJ 1398 Square Coins

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 // Author: Tanky Woo
// HDOJ 1398
#include <iostream>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1398 Square Coins》有7个想法

  1. 在k遍历指数时把k+=i变成了k+=i*i;????这是问什么呢?我是菜鸟,不太懂哈,能解释一下不?灰常感谢!!1

    1. 题目不是说了吗。。

      “……their values are square numbers……”

      要不是没理解题意,要不就是没理解母函数。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注