网站建设工作计划,做网站对企业的好处,湛江建设局网站,做网站需要交管理费吗题意#xff1a;就是给出二个数N#xff0c;和k#xff0c;有1~k种钱币#xff0c;每种都 是无限个#xff0c;用这些种类的钱币可以组合成总钱N有多少种方式。 解题#xff1a;这就是一个完全背包#xff0c;把N看成容量#xff0c;钱币的类型值为 花费和价值。与记录…
题意就是给出二个数N和k有1~k种钱币每种都 是无限个用这些种类的钱币可以组合成总钱N有多少种方式。 解题这就是一个完全背包把N看成容量钱币的类型值为 花费和价值。与记录有多少种路径的走法一样但要注意的是 这里输出的数据会很大会超出long long型所以用两个 long long 型来表示一个大数。分别是高位和低位低位不 超过10^18也就是有17位数。
Time limit 1000 ms
Memory limit 65536 kB
OS Linux
Source USACO 2006 January Silver
Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are: 1 US$3 1 US$21 US$3 2 US$11 US$2 3 US$12 US$2 1 US$15 US$1
Write a program than will compute the number of ways FJ can spend N dollars (1 N 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 K 100).
Input
A single line with two space-separated integers: N and K.
Output
A single line with a single integer that is the number of unique ways FJ can spend his money.
Sample Input
5 3
Sample Output
5
题意就是给出二个数N和k有1~k种钱币每种都 是无限个用这些种类的钱币可以组合成总钱N有多少种方式。
解题这就是一个完全背包把N看成容量钱币的类型值为 花费和价值。与记录有多少种路径的走法一样但要注意的是 这里输出的数据会很大会超出long long型所以用两个 long long 型来表示一个大数。分别是高位和低位低位不 超过10^18也就是有17位数。数据较弱可不对低位为零数位补充分析
#includeiostream
#includealgorithm
#includestring.h
using namespace std;
const long long M100000000000000000;
int m,n;
long long dp[10010],u[10010];/*用dp数组记录19位以上的数u数组记录19位以下的数*/
int main()
{while(cinmn){memset(dp,0,sizeof(dp));u[0]1;for(int i1; in; i)for(int ji; jm; j){dp[j]dp[j-i];u[j]u[j-i];if(u[j]M){dp[j]u[j]/M;u[j]%M;}}if(dp[m])coutdp[m];coutu[m]endl;}return 0;
}
较精准代码
#includeiostream
#includealgorithm
#includestring.h
using namespace std;
const long long M100000000000000000;
int m,n;
long long dp[10010],u[10010];/*用dp数组记录19位以上的数u数组记录19位以下的数*/
int main()
{while(cinmn){memset(dp,0,sizeof(dp));u[0]1;for(int i1; in; i)for(int ji; jm; j){dp[j]dp[j-i];u[j]u[j-i];if(u[j]M){dp[j]u[j]/M;u[j]%M;}}long long ansu[m];int sum0;while(ans)/*可能出现低位位数不够的问题故加零*/{sum;ans/10;}if(dp[m]){coutdp[m];while(sum17){sum;cout0;}}coutu[m]endl;}return 0;
}
/*题目意思就是给出二个数N和k有1~k种钱币每种都
是无限个用这些种类的钱币可以组合成总钱N有多少种方式。*/
/*解题这就是一个完全背包把N看成容量钱币的类型值为
花费和价值。与记录有多少种路径的走法一样但要注意的是
这里输出的数据会很大会超出long long型所以用两个
long long 型来表示一个大数。分别是高位和低位低位不
超过10^18也就是有17位数。
*/
