发现一位专门用SQL解各种谜题的高人！

〇〇 · 发表于 2012-8-13 07:38

[ 本帖最后由〇〇于 2012-8-13 07:38 编辑 ]

〇〇发表于 2012-8-13 07:36
How to simulate DML Operations on XML data using XU (XQuery Update)
How to validate XML data using  ...

uva 674 - Coin Change
分类： ACM----动态规划 2012-08-13 01:02 128人阅读评论(0) 收藏举报
点击打开链接

题目意思：有5种硬币 1 ， 5 ， 10  ， 25  ， 50 ，现在给我们一个数n，求用这5种硬币组成和为n的总方案数是多少

解题思路：动态规划
                  1:如果硬币只由1分组成，那么总方案数就是1
                  2:如果硬币由1和5组成，那么总方案数就是1+s1 (s1为1和5组成的方案)
                  .
                  .
                  .
                  6:如果硬币由1，5，10，25，50组成，那么总方案数就是1+s1+s2+s3+s4+s5
                  题目给出的数据n最大为7489，那么我们采用的是先把所有的值的拆分的总方案数求出来（也就是打表），然后输入一个我么直接输出即可。
                  思路：我们用type[5]数组存储5种硬币，设dp[j]表示用前i+1种（type[0]....type）组成价值为j的总方案数，那么我么就可以直接两重循环去枚举每一个价值j，求出所有的数据，最后查找输出。

代码：

[cpp] view plaincopyprint?//（没有优化）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 8000

int type[5] = {1,5,10,25,50};
int dp[5][MAXN];//用int类型即可，如果MAXN上万要用unsigned long long
int n , ans;

//打表处理好所有的数据
void solve(){
for(int i  = 0 ; i < 5 ; i++){
      for(int j = 0 ; j < MAXN ; j++){
         if(i == 0 || j == 0) dp[j] = 1;//i为0说明只由1组成那么dp[j]为1，j为0说明价值为0的组成方案只有1种（如果看成0则会WA）
         else dp[j] = 0;//其它全部初始化为0
      }
}
for(int i = 1 ; i < 5 ; i++){//i-1出现，那么从1开始枚举
      for(int j = 1 ; j < MAXN ; j++){
         for(int k = 0 ; k*type <= j ; k++)//k个type，注意必须从0开始
            dp[j] += dp[i-1][j-k*type];//加上前面的方案数
   }
}
}

int main(){
//freopen("input.txt" , "r" , stdin);
solve();
while(scanf("%d" , &n) != EOF){
      for(int i = 4 ; i >= 0 ; i--){
         if(dp[n]) { ans =  dp[n] ; break;}//从末尾开始查找只要有一个不为0就是答案
      }
      printf("%d\n" , ans);
}
return 0;
}




//（将二维优化成一维）优化后的代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 8000

int type[5] = {1,5,10,25,50};
int dp[MAXN];//dp表示价值i的总的方案数
int n , ans;

//打表处理好所有的数据
void solve(){
memset(dp , 0 , sizeof(dp)) ; dp[0] = 1;//注意dp[0] = 1这个条件
for(int i = 0 ; i < 5 ; i++){
      for(int j = 1 ; j < MAXN ; j++){
      if(j-type >= 0) dp[j] += dp[j-type];//累加起来
   }
}
}

int main(){
//freopen("input.txt" , "r" , stdin);
solve();
while(scanf("%d" , &n) != EOF) printf("%d\n" , dp[n]);
return 0;
}

//（没有优化）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 8000

int type[5] = {1,5,10,25,50};
int dp[5][MAXN];//用int类型即可，如果MAXN上万要用unsigned long long
int n , ans;

//打表处理好所有的数据
void solve(){
for(int i  = 0 ; i < 5 ; i++){
      for(int j = 0 ; j < MAXN ; j++){
         if(i == 0 || j == 0) dp[j] = 1;//i为0说明只由1组成那么dp[j]为1，j为0说明价值为0的组成方案只有1种（如果看成0则会WA）
         else dp[j] = 0;//其它全部初始化为0
      }
}
for(int i = 1 ; i < 5 ; i++){//i-1出现，那么从1开始枚举
      for(int j = 1 ; j < MAXN ; j++){
         for(int k = 0 ; k*type <= j ; k++)//k个type，注意必须从0开始
            dp[j] += dp[i-1][j-k*type];//加上前面的方案数
   }
}
}

int main(){
//freopen("input.txt" , "r" , stdin);
solve();
while(scanf("%d" , &n) != EOF){
      for(int i = 4 ; i >= 0 ; i--){
         if(dp[n]) { ans =  dp[n] ; break;}//从末尾开始查找只要有一个不为0就是答案
      }
      printf("%d\n" , ans);
}
return 0;
}

//（将二维优化成一维）优化后的代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 8000

int type[5] = {1,5,10,25,50};
int dp[MAXN];//dp表示价值i的总的方案数
int n , ans;

//打表处理好所有的数据
void solve(){
memset(dp , 0 , sizeof(dp)) ; dp[0] = 1;//注意dp[0] = 1这个条件
for(int i = 0 ; i < 5 ; i++){
      for(int j = 1 ; j < MAXN ; j++){
      if(j-type >= 0) dp[j] += dp[j-type];//累加起来
   }
}
}

int main(){
//freopen("input.txt" , "r" , stdin);
solve();
while(scanf("%d" , &n) != EOF) printf("%d\n" , dp[n]);
return 0;
}