51Nod 1101 换零钱

 1 //完全背包的变形
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int MOD = 1e9 + 7;
 8 const int maxn = 100000 + 5;
 9 int a[13] = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 };
10 int dp[maxn];
11 
12 int main(){
13     ios::sync_with_stdio(false);
14     int n;
15     cin >> n;
16     memset(dp, 0, sizeof(dp));
17     dp[0] = 1;
18     for (int i = 0; i < 13; i++){
19         for (int j = a[i]; j <= n; j++){
20             dp[j] = (dp[j] + dp[j - a[i]]) % MOD;
21         }
22     }
23     cout << dp[n] << endl;
24 
25     system("pause");
26     return 0;
27 }