题目
代码
#include <bits/stdc++.h>
using namespace std;
int f[1010][510];
int main()
{int n, m, k;cin >> n >> m >> k;int c = 0;for(int i = 1; i <= k; i++){int cost, hp;cin >> cost >> hp;for(int j = n; j >= cost; j--){for(int t = m; t > hp; t--){f[j][t] = max(f[j][t], f[j-cost][t-hp] + 1);c = max(c, f[j][t]);}}}int r;if(c == 0) r = 0;else{r = 510;for(int j = 1; j <= m; j++){if(f[n][j] == c){r = j;break;}}r--;}cout << c << ' ' << m-r;return 0;
}
注意
- hp不能为0,因此不能从 的状态转移
- 因为hp有1不是因为收服小精灵而记录的,因此要