HDUOJ ------1398
2024-10-07 21:57:15
http://acm.hdu.edu.cn/showproblem.php?pid=1398
Square Coins
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6697 Accepted Submission(s): 4521
Problem Description
People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17^2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, ..., and 289-credit coins, are available in Silverland.
There are four combinations of coins to pay ten credits:
There are four combinations of coins to pay ten credits:
ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.
Your mission is to count the number of ways to pay a given amount using coins of Silverland.
Input
The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.
Output
For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.
Sample Input
2 10 30 0
Sample Output
1 4 27
Source
Recommend
Ignatius.L
母函数.......
#include<iostream>
using namespace std;
int main()
{
int n,i,j,k;
while(cin>>n,n)
{
int c1[]={},c2[]={};
for(j=;j<=n;j++)
{
c1[j]=;
}
for(i=;i*i<=n;i++)
{
for(j=;j<=n;j++)
{
for(k=;k+j<=n;k+=i*i)
{
c2[k+j]+=c1[j];
}
}
for(j=;j<=n;j++)
{
c1[j]=c2[j];
c2[j]=;
}
}
cout<<c1[n]<<endl;
}
return ;
}
最新文章
- Windows Server 2012 NIC Teaming介绍及注意事项
- hihoCoder 1385 : A Simple Job(简单工作)
- git 换行符LF与CRLF转换问题
- stack+DFS ZOJ 1004 Anagrams by Stack
- 负载均衡LVS集群详解
- PHP学习心得(四)——基本语法
- iOS 9 适配
- java小算法—大衍数列
- Oracle查询表结构的常用语句
- mySQL内存及虚拟内存优化设置
- hdu--1711--kmp应用在整形数组--Number Sequence
- 批处理注册dll时候 遇到错误:模块已加载,但对***dll的调用失败
- hdu 5439(找规律)
- 分享:大型Web网站架构演变之9大阶段
- Rhel6.5 相关操作
- AXI总线介绍
- synchronized的一些记录
- 【win10】更改资源管理器显示:快速访问和此电脑
- 使用badblocks检测坏块
- glassfish--服务搭建