找零钱

找零钱

时间: 1ms        内存:64M

描述:

我们知道人民币有1、2、5、10、20、50、100这几种面值。
现在给你 n(1≤n≤250)元,让你计算换成用上面这些面额表示且总数不超过100张,共有几种。
比如4元,能用4张1元、2张1元和1张2元、2张 2元,三种表示方法。

输入:

输入有多组,每组一行,为一个整合n。
输入以0结束。

输出:

输出该面额有几种表示方法。

示例输入:

1
4
0

示例输出:

1
3

提示:

参考答案(内存最优[948]):

#include "stdio.h"
#include "string.h"
int c1[101][251],c2[101][251];
int z[7]={1,2,5,10,20,50,100};
int main()
{
	int t,i,sum,j,k,count,p,zz;
		memset(c1,0,sizeof(c1));
		memset(c2,0,sizeof(c2));
		sum=0;
		count=0;
		for(i=0;i<=100;i+=1)
			c1[i][i]=1;
		for(i=1;i<7;i++)
		{
		    for(p=0;p<=100;p++)
			for(j=0;j<=250;j++)
				for(k=0;(k+p<=100)&&(j+k*z[i]<=250);k++)
				{
					c2[k+p][j+k*z[i]]+=c1[p][j];
				}
            for(p=0;p<=100;p++)
			for(j=0;j<=250;j++)
			{
				c1[p][j]=c2[p][j];
				c2[p][j]=0;
			}
		}
	while(scanf("%d",&t)&&t!=0)
	{zz=0;
	    for(i=0;i<=100;i++)
		zz+=c1[i][t];
		printf("%d\n",zz);
	}
	return 0;
}

参考答案(时间最优[12]):

#include <iostream>  
using namespace std;  
//int COUNT;  
int cost[]={1,2,5,10,20,50,100};  
int main()  
{  
   // void Quicksearch(int,int=0,int=0);  
    int n,i; 
    int s[251][102][8]={0};    //  s[a][b][c]   a>=b   a当前总值  b当前使用张数   c 最高使用某一类时的方案数 
    for(i=0;i<7;i++) 
    { 
        s[ cost[i] ][1][i]=1; 
    } 
    s[1][101][0]=1; 
    for(i=2;i<251;i++)   // s[2][1][1]=1;   s[2][2][0]=1; 
    { 
        for(int j=1;j<=i&&j<101;j++) 
        {    
            for(int k=6;k>=0;k--) 
            { 
                if(i>cost[k]) 
                { 
                    for(int l=k;l>=0;l--) 
                    { 
                        s[i][j][k]+=s[ i-cost[k] ][j-1][l]; 
                    } 
                } 
                s[i][j][7]+=s[i][j][k]; 
            } 
            s[i][101][0]+=s[i][j][7]; 
        } 
    } 
    while(cin>>n&&n!=0)  
    {    
        cout<<s[n][101][0]<<endl; 
    }  
    return 0;  
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

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