UVa 674 Coin Change【记忆化搜索】

题意：给出1,5,10,25,50五种硬币，再给出n,问有多少种不同的方案能够凑齐n

自己写的时候写出来方案数老是更少（用的一维的）

后来搜题解发现，要用二维的来写

http://blog.****.net/keshuai19940722/article/details/11025971

这一篇说的是会有面值的重复问题，还不是很理解

还有就是一个预处理的问题，看了题解之后再自己写，很习惯的把处理dp数组写到while循环里面，一直tle

后来看到这篇题解

http://www.cnblogs.com/scau20110726/archive/2012/12/25/2832968.html

因为题目没有说会有多少组数据，如果把处理dp数组放在while循环里面的话，如果给出一个10w组的数据，那肯定就会超时(相当于每算一次，就要处理一次dp数组)

所以就把预处理放在外面就好啦

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 #define mod=1e9+7;

 using namespace std;

 typedef long long LL;

 const int INF = 0x7fffffff;

 const int maxn=;

 LL dp[maxn][];

 int coin[]={,,,,};

 LL dfs(int s,int i){

     if(dp[s][i]!=-) return dp[s][i];

     dp[s][i]=;

     for(int j=i;j<&&s>=coin[j];j++)

     dp[s][i]+=dfs(s-coin[j],j);

     return dp[s][i];

 }

 int main(){

     int n;

         memset(dp,-,sizeof(dp));

         for(int i=;i<;i++) dp[][i]=;

     while(scanf("%d",&n)!=EOF){

         printf("%lld\n",dfs(n,));

     }

     return ;

 }

秒客网

UVa 674 Coin Change【记忆化搜索】

相关文章