警钟长鸣-----找零钱

蒟蒻的我在这个题上花了40分钟还超时了(悲

不说了先上超时的代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int res,n,a[]={1,2,5,10,20,50,100},x;
 4 void dfs(int st,int num,int id)
 5 {
 6     if(st==0){res++;return;}
 7     if(st<0||num>100||id>6) return;
 8     dfs(st-a[id],num+1,id);
 9     dfs(st,num,id+1);
10 }
11 int main()
12 {
13     while(cin>>n&&n!=0)
14     {
15         res=0,x=6;
16         //for(int i=0;i<=6;i++) if(a[i]>=n) {x=i;break;} 
17         dfs(n,1,0);
18         cout<<res<<endl;
19     }
20     return 0;
21 }

简单的dfs,唉,没想到还是要动态规划,动态规划写的很详细,可以仔细理解一下

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int f[251][102][8],a[]={1,2,5,10,20,50,100},n;//a是每张票子的额度
 4 //f有三个状态,表示i元时,用j次钞票,并且i,j的时候用的a[k]的价值,此时的最大值
 5 int main()
 6 {
 7     //先准备好所有的状态,然后输入一次输出一次,简化时间;
 8     for(int i=0;i<7;i++) f[a[i]][1][i]=1;//初始化
 9     for(int i=1;i<=250;i++)
10     {
11         for(int j=1;j<=i&&j<101;j++)//条件判断
12         {
13             for(int k=6;k>=0;k--)//枚举六张票
14             {
15                 if(i>a[k])//如果i元能被这张票子加上去
16                     for(int l=k;l>=0;l--)//看看能不能被别的票子加上去
17                         f[i][j][k]+=f[i-a[k]][j-1][l];//更新状态
18                         //这时最大值时是由上一次被使用的票子,然后用每一张票的情况
19                         //可能会有点难理解,通俗点就是,i元之前,是i-a[k]元
20                         //f[i-a[k]][j-1][l]是i-a[k]元的所有情况
21                 f[i][j][7]+=f[i][j][k];//更新状态
22             }
23             f[i][101][0]+=f[i][j][7];//更新状态
24         }
25     }
26     while(cin>>n&&n!=0) cout<<f[n][101][0]<<endl;
27     return 0;
28 }