uva 10313 Pay the Price （DP）

uva 10313 Pay the Price （DP）

uva 10313 Pay the Price

題目大意：現在有300種面額的硬幣（1~300），給出一個金額數，問這300種面額的硬幣組成該金額數的方式有多少種。注意：該題的輸入有三種模式，1個數n：n為金額數；2個數n, a：n為金額數，a為硬幣個數上限；3個數n， a，b：n為金額數，a b為硬幣個數的下限和上限。

解題思路：dp[i][j]表示面額i的金額，在硬幣數不超過j的情況下，有幾種組成方式。這個題目涉及到一個結論，用不超過i個硬幣湊出面值j的方案種數，是和用面值不超過i的硬幣湊出面值j的方案種數是相同的。那麼如果使用了面值j，對應方案種數就應該加上dp[i-j][j]，如果不使用面值j，對應的方案種數就應該加上dp[i][j-1]。狀態轉移方程為dp[i][j]=dp[i?j][j]+dp[i][j?1]。

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
int n, a, b;
ll dp[305][305];
void init() {
    for (int i = 0; i <= 300; i++) {
        if (!i) dp[i][0] = 1;
        else dp[i][0] = 0;
        for (int j = 1; j <= 300; j++) {
            if (i >= j) {
                dp[i][j] = dp[i - j][j] + dp[i][j - 1];
            } else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
}
int main() {
    init();
    while (scanf("%d", &n) != EOF) {
        char temp;
        a = 1, b = n;
        scanf("%c", &temp);
        int flag = 0;
        if (temp == ' ') {
            flag = 1;
            scanf("%d", &a);
            scanf("%c", &temp);
            if (temp == ' ') {
                flag = 2;
                scanf("%d", &b);
            }
        }
        if (a > 300) a = 300;
        if (b > 300) b = 300;
        if (!flag) {
            printf("%lld\n", dp[n][n]);
        } else if (flag == 1) {
            printf("%lld\n", dp[n][a]);
        } else if (flag == 2) {
            if (!a) {
                printf("%lld\n", dp[n][b]);
            } else printf("%lld\n", dp[n][b] - dp[n][a - 1]);
        }
    }
    return 0;
}