题目大意:
有0~300这300种价值的金额。 现在可能给出参数:
1个:n, 输出可以组成价值n的方式的个数。
2个:n, a, 输出用个数小于a个硬币的组成价值n的方式的个数。
3个:n, a, b, 输出用个数大于a和小于b个硬币组成价值n的方式的个数。
解题大意:
参考了其他人的说明才知道需要用到Ferrers图像的一个结论进行解题,该结论为:用不超过j个硬币凑出面值i的方案种数,是和用面值不超过j的硬币凑出面值i的方案种数是相同的。
所以本题就可以认为是用面值不超过j的硬币凑出面值i的方案中数。设dp[i][j]表示用不超过面值j的硬币凑出面值i的方案种数,那么状态转移方程为:
若i>j,则dp[i][j] += dp[i-j][j]; 表示若硬币面值小于i,则用价值为j的硬币凑成i的数量等于自身的数量加上用价值为j的硬币凑成i-j的数量,此外若j-1>0,dp[i][j] += dp[i][j-1]; 即还要再加上用价值为j-1的硬币凑成i的数量。
代码如下:
#include <iostream> #include <algorithm> #include <vector> #include <string> #include <cmath> #include <fstream> #include <sstream> #include <map> using namespace std; #define LOOP(X,Y) for( int X = 0; X < Y; X++ ) #define LOOPP(X, Y, Z) for( int X = Y; X < Z; X++ ) #define SLOOP(X,Y) for( int X = Y; X >= 0; X-- ) #define SLOOPP(X, Y, Z) for( int X = Y; X >= Z; X-- ) #define OPENFILE(PATH) ifstream fin; fin.open(PATH); #define APENDFILE(PATH) char * file = PATH; ofstream fout( file, ios::out | ios::app ); #define PB push_back #define ULL unsigned long long #define LL long long int coins[301]; LL dp[301][301]; int main() { OPENFILE("test.txt"); string line; int temp; vector<int> v; memset( dp, 0, sizeof( dp ) ); dp[0][0] = 1; //先算出所有可能,即预处理一下。 for( int i = 0; i <= 300; i++ ) { for( int j = 1; j <= 300; j++ ) //j不能从0开始,因为硬币的价值至少为1,若从0开始,最后结果会翻一倍。 { if( i - j >= 0 ) dp[i][j] += dp[i-j][j]; if( j - 1 >= 0 ) dp[i][j] += dp[i][j-1]; } } while(getline( fin, line )) { istringstream is(line); while( is>>temp ) { v.PB(temp); } if( v.size() == 1 ) cout<<dp[v[0]][v[0]]<<endl; else if( v.size() == 2 ) cout<<dp[v[0]][v[1]]<<endl; else cout<<dp[v[0]][v[2]]-dp[v[0]][v[1]-1]<<endl; v.clear(); } return 0; }
相关推荐
DP – 完全背包 – Pay the Price – UVA – 10313 题意: 有n种货币,面值依次是1,2,…,n,现需在一些限制的情况下凑出n元。:有n种货币,面值依次是1,2,…,n,现需在一些限制的情况下凑出n元。:有n种货币,面值...
UVA 10474
Uva 100 ,问题是The 3n+1 probelm ,可以ac的代码
UVA109的题解,经测试完全正确,还附有题解。
uva272
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
uva_trilearn2002 源代码
主要是uvaoj习题相关题目 练习题目
PDF试题