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; }