百练宠物小精灵之收服

思路：

dp。

实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int N, M, K;
 7 int a[105], b[105], dp[1005][505];
 8 
 9 void solve()
10 {
11     for (int i = K - 1; i >= 0; i--)
12     {
13         for (int j = N; j >= 0; j--)
14         {
15             for (int k = M; k >= 0; k--)
16             {
17                 dp[j][k] = dp[j][k];
18                 if (j >= a[i] && k >= b[i])
19                 {
20                     dp[j][k] = max(dp[j][k], dp[j - a[i]][k - b[i]] + 1);
21                 }
22             }
23         }
24     }
25     int maxN = 0, costM = 0;
26     for (int i = 0; i < M; i++)
27     {
28         if (dp[N][i] > maxN)
29         {
30             maxN = dp[N][i];
31             costM = i;
32         }
33     }
34     cout << maxN << " " << M - costM << endl;
35 }
36 int main()
37 {
38     cin >> N >> M >> K;
39     for (int i = 0; i < K; i++)
40     {
41         cin >> a[i] >> b[i];
42     }
43     solve();
44     return 0;
45 }

百练 宠物小精灵之收服

百练宠物小精灵之收服