C语言OJ 提交提示 “Time Limit Exceed”Description 我们知道人民币有1、2、5、10、20、50、100这几种面值.现在给你n(1≤n≤250)元,让你计算换成用上面这些面额表示且总数不超过100张,共有几种.比如4

C语言OJ 提交提示 “Time Limit Exceed”Description 我们知道人民币有1、2、5、10、20、50、100这几种面值.现在给你n(1≤n≤250)元,让你计算换成用上面这些面额表示且总数不超过100张,共有几种.比如4
C语言OJ 提交提示 “Time Limit Exceed”
Description
我们知道人民币有1、2、5、10、20、50、100这几种面值.
现在给你n(1≤n≤250)元,让你计算换成用上面这些面额表示且总数不超过100张,共有几种.
比如4元,能用4张1元、2张1元和1张2元、2张2元,三种表示方法.
Input
输入有多组,每组一行,为一个整合n.
输入以0结束.
Output
输出该面额有几种表示方法.
Sample Input
1
4
0
Sample Output
1
3
下面是我的代码：
#include
int main()
{ int i,j,k,p,q,r,s,n,m,n1,n2,n3,n4,n5,n6;
while(scanf("%d",&n),n)
\x05{\x05m=0;n1=n/2;n2=n/5;n3=n/10;n4=n/20;n5=n/50;n6=n/100;
\x05\x05for(i=0;i

C语言OJ 提交提示 “Time Limit Exceed”Description 我们知道人民币有1、2、5、10、20、50、100这几种面值.现在给你n(1≤n≤250)元,让你计算换成用上面这些面额表示且总数不超过100张,共有几种.比如4
你这个需要剪枝,下面我写这个是做了简单的剪枝的.
虽然不敢保过,但也算个思路给你吧.
#include
int cont=7;
int maxcount=1000000;
int miane[cont]={100,50,20,10,5,2,1};
int count=0;
int sum=0;
void back(int ci,int left);
int main()
{
back(0,100000);
printf("%d\n",sum);
return 0;
}
void back(int ci,int left)
{
int i;
if(ci==cont)
{
return;
}
for(i=0;left-i*miane[ci]>=0;i++)
{
if(i>0)
{
count++;
}
if(count>maxcount)
{
break;
}
if(left-i*miane[ci]==0&&i!=0)
{
sum++;
}
back(ci+1,left-i*miane[ci]);
}
count-=i-1;
}