蒟蒻的我在这个题上花了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 }