uva 10313 Pay the Price（完全背包）

题目连接：10313 - Pay the Price

题目大意：有0~300这300种价值的金额。

现在可能给出参数：

1个：n, 输出可以组成价值n的方式的个数。

2个：n, a输出用个数小于a的价值组成价值n的方式的个数。

3个：n, a, b输出用个数大于a和小于b组成价值n的方式的个数。

解题思路：完全背包的问题， 状态转移方程dp[i][j] 表示价值i用j个硬币组成的方式种类， 转移方程dp[j][k] += dp[j - i][k - 1]。

#include <stdio.h>#include <string.h>#include <stdlib.h>const int N = 305;long long dp[N][N];void Init() {    memset(dp, 0, sizeof(dp));    dp[0][0] = 1;    for (int i = 1; i <= 300; i++) {for (int j = i; j <= 300; j++) {    for (int k = 1; k <= 300; k++)dp[j][k] += dp[j - i][k - 1];}     }}int main() {    Init();    int n, a, b;    char str[N];    while (gets(str)) {int flag = sscanf(str, "%d%d%d", &n, &a, &b);long long sum = 0;if (a > 300)a = 300;if (b > 300)b = 300;if (flag == 1) {    for (int i = 0; i <= n; i++)sum += dp[n][i];}else if (flag == 2) {    for (int i = 0; i <= a; i++)sum += dp[n][i];}else if (flag == 3) {    for (int i = a; i <= b; i++)sum += dp[n][i];}printf("%lld\n", sum);    }    return 0;}