现在的位置: 首页 > 综合 > 正文

hdu 1398 Square Coins(简单背包)

2019年04月13日 ⁄ 综合 ⁄ 共 1948字 ⁄ 字号 评论关闭

Square Coins

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7300    Accepted Submission(s): 4945

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:

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   |   We have carefully selected several similar problems for you:  1028 2152 2082 2079 2069 
 

题意:

有面值分别为。1,4,9,.......17^2的硬币无数多个。问你组成面值为n的钱的方法数。

思路:

典型的背包问题。

dp[i][j]表示用到前i种面值的硬币组成面值为j的钱的方法数。那么dp[i[j]=dp[i-1][j-k*val]。val为枚举当前硬币的面值。k=0,1,2..j-k*val>0.由于状态转移只会用到两层的值。所以我们可以压缩下空间。用一维空间来递推。dp[j]表示组成面值j的方法数。dp[j]+=dp[j-val]。就可以顺利转移了。

代码如下:

#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=100010;
typedef __int64 ll;
int f[500],coin[20];

int main()
{
    int i,j,n;

    for(i=1;i<=17;i++)
        coin[i]=i*i;//预处理出物品的重量
    memset(f,0,sizeof f);
    f[0]=1;
    for(i=1;i<=17;i++)
        for(j=coin[i];j<=300;j++)
            f[j]+=f[j-coin[i]];
    while(scanf("%d",&n),n)
        printf("%d\n",f[n]);
    return 0;
}


抱歉!评论已关闭.