程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> uva 10313 Pay the Price (DP)

uva 10313 Pay the Price (DP)

編輯:關於C++

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;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved