SubmitStatusWebBoard（完全背包）

/*完全背包

http://www.acmore.net/problem.php?id&＃61;1081

SubmitStatusWeb Board

Description

母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。 [In their own rebellious way],&＃xff0c;他们对货币的数值感到好奇。传统地&＃xff0c;一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。举例来说, 使用一个货币系统 {1,2,5,10,...}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2&＃43;2x1, 3x5&＃43;2&＃43;1,等等其它。写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数将会适合long long (C/C&＃43;&＃43;) 和 Int64 (Free Pascal)。

Input

货币系统中货币的种类数目是 V 。 (1<&＃61; V<&＃61;25) 要构造的数量钱是 N 。 (1<&＃61; N<&＃61;10,000) 第 1 行: 二整数&＃xff0c; V 和 N 第 2 ..V&＃43;1行&＃xff1a; 可用的货币 V 个整数　(每行一个　每行没有其它的数)。

Output

单独的一行包含那个可能的构造的方案数。

Sample Input

3 10

1 2 5

Sample Output

HINT

Source

USACO Train

//解析&＃xff1a;&＃xff0c;最简单的背包题。没想到这一点。把它看成整数划分&＃xff0c;看了第一个人的思路很重要&＃xff0c;会影响每个人的思路&＃xff0c;没那么复杂。很多题目可以往DP上看看

SubmitStatusWeb Board

Memory Time Language Code Length Submit Time

1512 570 B

C&＃43;&＃43;/Edit

#include #include #include using namespace std; const int maxn&＃61;10000&＃43;10; long long dp[maxn];//dp[j]表示当面值为j时的方案数 int a[28]; int main() { int n,m; int i,j; while(scanf("%d%d",&n,&m)!&＃61;EOF) { for(i&＃61;0;iscanf("%d",&a[i]); memset(dp,0,sizeof(dp)); dp[0]&＃61;1; for(i&＃61;0;ifor(j&＃61;a[i];j<&＃61;m;j&＃43;&＃43;) dp[j]&＃43;&＃61;dp[j-a[i]];//求方案数 printf("%lld\n",dp[m]); } return 0; }