找零钱
时间: 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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。