uva 10313 Pay the Price（完全背包） - c++编程基础

题目大意：有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   
#include   
#include   
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;  
}