B - 最少硬币问题（DP）

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string.h>
 4 #define inf 0x3f3f3f3f
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     int n, m, i, j, k;
10     int T[15], Coin[15], dp[20005];
11     cin >> n;
12     for(i=0;i<n;i++)
13     {
14         cin >> Coin[i] >> T[i];
15     }
16     cin >> m;
17     memset(dp, inf, sizeof(dp));
18     dp[0] = 0;
19     for(i=0;i<n;i++)
20     {
21         for(j=0;j<T[i];j++)
22         {
23             for(k=m;k>=Coin[i];k--)
24             {
25                 dp[k] = min(dp[k], dp[k-Coin[i]]+1);
26             }
27         }
28     }
29     if(dp[m]==inf) cout << "-1" << endl;
30     else cout << dp[m] << endl;
31     return 0;
32 }